Discovering the Magic of Heap in Java

Introduction: Imagine a magical box that organizes things in a special way, making tasks faster and smoother. In the world of computer science, such magic exists in the form of a Heap, and today, we’re diving into a Java implementation of this powerful tool.

Pic

import java.util.ArrayList;
import java.util.List;

class Heap<T extends Comparable<T>> {
    private List<T> list;//Declaring a list to Store the items

    public Heap() {
        //Constructor to initialize the list.
        list = new ArrayList<>();
    }

    private void swap(int first, int second) {
        //Swap Method for Swapping 2 items of given indices
        T temp = list.get(first);
        list.set(first, list.get(second));
        list.set(second, temp);
    }

    private int Parent(int index) {
        //Will return the parents index of the given index
        //    0
        //   /  \
        //  1    2
        return (index - 1) / 2;
    }

    private int left(int index) {
        //will return the left of parent node
        //        0
        //       /  \
        //      1    2     (2*0+1)=1 for left && (2*0+2) for right
        //        1
        //       /  \
        //      3    4      (2*1+1)=3 for left  && (2*1+2)=4 for right
        return (2 * index + 1);
    }

    private int right(int index) {
        //will return right of the parent node
        //explained above
        return (2 * index + 2);
    }

    public void insert(T value) {
        //inserting the value.
        list.add(value);
        //checking if swap is necessary
        upHeap(list.size() - 1);//UpHeap is done from last element bcoz element will be added on the last place and
        //it will be compared with its parent wheather it satifies the condition
    }

    public void upHeap(int index) {
        if (index == 0) return;
        int p = Parent(index);
        if (list.get(index).compareTo(list.get(p)) < 0) {
            swap(index, p);//if the last elemnt is less than its parent means swap is necessary
            upHeap(p);//recursion to check if its less than its upcoming parents or not
        }
    }

    public T delete() throws Exception {
        //step 1 remove the first element
        //step 2 remove last elemnt and place it at place from where it was removed
        //step 3 chevk for left and right smaller(in this case)
        //swap the elemnts and continue it is placed at right place
        if (list.size() == 0) {
            throw new Exception("Removing from Empty Heap (Aila pagal hai kya)");
        }
        T temp = list.get(0);//getting the first item.
        T last = list.remove(list.size() - 1);//
        if (!list.isEmpty()) {
            list.set(0, last);
            downHeap(0);
        }
        return temp;
    }
    public void downHeap(int index){
        int min=index;
        int left=left(index);
        int right=right(index);
        if(left< list.size() && list.get(min).compareTo(list.get(left))>0){
            min=left;
        }
        if(right< list.size() && list.get(min).compareTo(list.get(right))>0){
            min=right;
        }
        if(min!=index){
            swap(min,index);
            downHeap(min);
        }
    }
    //Array sort(or say HeapSort)
    public ArrayList<T>  heapSort() throws Exception{
        ArrayList<T> data=new ArrayList<>();
        while (!list.isEmpty()){
            data.add(this.delete());
        }
        return data;
    }
}

The Heart of the Heap: The Heap Class Our main character is the Heap class, a superhero that starts with an empty list, thanks to Java's ArrayList. This list becomes the canvas for creating order and efficiency using the magic of heaps.

Swapping and Shuffling: The Dance of Elements In the Heap’s world, elements can gracefully switch places using the swap method. It's like a dance move where two elements exchange spots, crucial for keeping the heap in perfect shape.

Navigating the Family Tree: Parent, Left, and Right Just like a family tree, heaps have parents and children. The Parent, left, and right methods are like a map that helps elements find their place in this hierarchical family, making sure everyone knows who their relatives are.

Adding a New Member: Insertion and Up-Heap When a new element joins the heap party with the insert method, it's like welcoming a new friend. But to keep things organized, the upHeap operation kicks in, making sure the newbie fits in properly by checking with its new buddies.

Saying Goodbye: Deletion and Down-Heap When an element leaves the party with the delete method, it's a bittersweet moment. The downHeap operation takes over, making sure the remaining elements adjust nicely without the departed friend.

Grand Finale: HeapSort As our story wraps up, the heapSort method steals the spotlight. It's like a grand show where elements take their final bows, each leaving the stage in a well-arranged order. The result? A perfectly sorted array, achieved through the magic of heapsort.

Conclusion: A Symphony of Order and Efficiency In the world of computer science, heaps are like magical conductors, making operations smooth and efficient. The Java implementation we explored isn’t just code; it’s a dance of elements, a symphony of order and efficiency. As you venture into coding adventures, let the beauty of heaps guide you towards creating harmonious and optimized algorithms.