Heap

Heap is a Data Structure that follows the following: It should be a Complete Binary Tree(CBT) and has a “Heap Order Property”

A complete Binary Tree (CBT) is a binary tree where every level is completely filled except the last level and the nodes are always added from the left or you can say is left-leaning.

There are two types of Heap

• Max Heap
• Min Heap

Max Heap

Child nodes value should be less than the root.

Min Heap

The child nodes will be greater than the root

Complete Binary Tree (BST) and array relation

At any ith index

left child -> ( 2 * i)index

right child -> (2 * i) + 1 index

Heap implemented using array

public class Heap {
    int[] arr = new int[100];
    int size = 0;

    /**
     * Algorithm
     *  - Insert at end
     *  - Move element to correct position
     *     - compare with parent and swap
     */
    void insert(int val){
        size = size + 1;
        int index = size;
        arr[index] = val;

        while(index > 1){
            int parent = index / 2;
            if(arr[parent] < arr[index]){
                swap(parent, index);
                index = parent;
            }else{
                return;
            }
        }
    }

    /**
     * Algorithm
     *  - Put last elemet to the root (first element)
     *  - remove last node
     *  - Propogate root note to its correct location
     */
    void delete() {
        if (size == 0) {
            System.out.println("Heap empty");
            return;
        }

        arr[1] = arr[size];
        size--;

        int i = 1;
        while (i < size) {
            {
                int leftIndex = 2 * i;
                int rightIndex = 2 * i + 1;

                if (leftIndex < size && arr[i] < arr[leftIndex]) {
                    swap(i, leftIndex);
                    i = leftIndex;
                } else if (rightIndex < size && arr[i] < rightIndex) {
                    swap(i, rightIndex);
                    i = rightIndex;
                } else {
                    return;
                }
            }
        }
    }

    void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    void display(){
        for(int i = 1; i <= size; i++){
            System.out.print(arr[i] + " ");
        }
    }

    /**
     * CBT (Complete Binary Tree)
     * (n/2 + 1) -> n
     */
    void heapify(int[] arr, int n, int i){
        int largest = i;
        int left = 2 * i;
        int right = 2 * i + 1;
        
        if(left < n && arr[largest] < arr[left]){
            largest = left;
        }
        
        if(right < n && arr[largest] < arr[right]){
            largest = right;
        }
        
        if(largest != i){
            swap(i, largest);
            heapify(arr, n, largest);
        }
    }

    public static void main(String[] args) {
        Heap heap = new Heap();
        heap.insert(50);
        heap.insert(2);
        heap.insert(40);
        heap.insert(30);
        heap.insert(20);
        heap.insert(10);

        heap.display();
    }
}