Brief

What is heap?

• A heap is a complete binary tree that follows the heap order property.

What is Complete Binary Tree (CBT)?

• A complete binary tree is a binary tree in which every level is completely filled except for the last level.

• Nodes are always added from the left.

Heap Order Property

There are 2 types of heaps

• Max heap: The root node is always the maximum of all the elements.

• Min heap: The root node is always the minimum of all the elements.

Operations

Insertion into heap

• We insert nodes row-wise from left to right. So, when we insert a node, it will be inserted at the end of the array.

  Hence, if the current node is i, then the child nodes are:

  • For zero-based index: left is 2i + 1 and right is 2i + 2.

  • For one-based index: left is 2i and right is 2i + 1.

• Similarly, in all cases, the parent of the ith node will be i/2.

public class CustomPriorityQueue {
    private int[] arr = new int[100];
    private int size;

    public CustomPriorityQueue() {
        size = 0;
    }
}

• If we insert a node at the end of the array for a max heap, we check whether the current node i is greater than its parent i/2. If it is, we swap them. We continue checking the current swapped node i/2 with its parent i/4. We stop this iteration whenever the parent node’s value is greater than the child’s.

• In this way, the newly inserted node will propagate up until it is no longer greater than its parent.

    public void add(int value){
        size+=1;
        int index = size;

        arr[index] = value;
        while(index!=1){

            if (arr[index/2]<arr[index]){
                swap(arr, index/2, index);
                index = index/2;
            }
            else{
                return;
            }
        }
    }

Insertion Visualization

Deletion

• Swap the first node with the last node.

• Remove the last node by decrementing the size.

• Propagate the root node to its correct position.

  • Check with the left and right child. If one of the children is greater than the parent, then swap.

  • Now go in the direction of the child that was swapped, meaning keep on checking the parent with its children and swap until the parent is larger than the children.

public void delete(){
    arr[0] = arr[size-1];

    size-=1;

    int index = 0;

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

        int largest = index;

        if(arr[leftIndex]>arr[index]){
            largest = leftIndex;
        }

        if (arr[rightIndex]>arr[index]) {
            largest = rightIndex;
        }

        if (index!=largest){
            swap(arr, index,largest);
            index = largest;
        }
        else break;
    }
}

Heapify

• Convert a given array into a heap.

• In a Complete Binary Tree (CBT), leaf nodes start from n/2 + 1 to n because if you take the last leaf node index as n - 1, then its parent is n/2. Hence, after n/2, all the nodes will be leaf nodes.

• We apply the heapify algorithm in reverse order, that is, from n/2 + 1 to 0. For each node, we treat it as the root node and apply the heapify algorithm to the entire subtree under it.

int[] arr = {54, 53, 55, 52, 50};
int n = arr.length;
for (int i=(n/2+1); i>=0; i--){
    CustomPriorityQueue.heapify(arr,arr.length, i);
}

• This is similar to the delete functionality, but this is a recursive approach. We compare the current root node with its children and swap with the larger child. Then we call heapify on the child node index that got swapped, and we keep heapifying until the leaf node is reached or there is no need to swap because the parent is the largest.

public static void heapify(int[] num, int n, int i){
    int largestIndex = i;
    int leftIndex = 2*i + 1;
    int rightIndex = 2*i + 2;

    if(leftIndex<n&& num[largestIndex]<num[leftIndex]){
        largestIndex = leftIndex;
    }

    if (rightIndex<n && num[largestIndex]<num[rightIndex]){
        largestIndex = rightIndex;
    }

    if (largestIndex!=i){
        swap(num,largestIndex,i);
        heapify(num,n,largestIndex);
    }
}

Heap Sort

• When we get the array, we directly apply the heapify algorithm to get the first maximum. Then we apply heapify again to get the next maximum. Similarly, we keep applying heapify to get the subsequent maximum values.

• Every time we get the maximum, we remove it from the array. Technically, we remove it by swapping the first node with the last node and decrementing the size by 1. In this way, we obtain the first maximum.

public static void heapSort(int[] nums){
    int size = nums.length;

    while (size>1){
        heapify(nums,size,0);
        swap(nums,0,size-1);
        size-=1;
    }
}

Important Note

• decreaseKey() is similar to the insertion logic, where the current node will propagate upwards.

• heapify() will propagate the current node downwards in the tree.

Code (Reference)

package heap;

import java.util.Arrays;

public class CustomPriorityQueue {
    private int[] arr = new int[100];
    private int size;

    public CustomPriorityQueue() {
        size = 0;
    }

    public void add(int value){

        size+=1;
        int index = size-1;

        arr[index] = value;
        while(index!=0){

            if (arr[index/2]<arr[index]){
                swap(arr, index/2, index);
                index = index/2;
            }
            else{
                return;
            }
        }
    }

    public void delete(){
        arr[0] = arr[size-1];

        size-=1;

        int index = 0;

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

            int largest = index;

            if(arr[leftIndex]>arr[index]){
                largest = leftIndex;
            }

            if (arr[rightIndex]>arr[index]) {
                largest = rightIndex;
            }

            if (index!=largest){
                swap(arr, index,largest);
                index = largest;
            }
            else break;
        }
    }

    public static void heapify(int[] num, int n, int i){
        int largestIndex = i;
        int leftIndex = 2*i + 1;
        int rightIndex = 2*i + 2;

        if(leftIndex<n&& num[largestIndex]<num[leftIndex]){
            largestIndex = leftIndex;
        }

        if (rightIndex<n && num[largestIndex]<num[rightIndex]){
            largestIndex = rightIndex;
        }

        if (largestIndex!=i){
            swap(num,largestIndex,i);
            heapify(num,n,largestIndex);
        }
    }

    public static void heapSort(int[] nums){
        int size = nums.length;

        while (size>1){
            heapify(nums,size,0);
            swap(nums,0,size-1);
            size-=1;
        }
    }

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

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        for (int i=1; i<=size; i++){
            res.append(arr[i]+" ");
        }
        return res.toString();
    }
}

Application

Problem

A binary heap is a Binary Tree with the following properties: (link)
1) Its a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at the root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

You are given an empty Binary Min Heap and some queries and your task is to implement the three methods insertKey, deleteKey, and extractMin on the Binary Min Heap and call them as per the query given below:
1) 1 x (a query of this type means to insert an element in the min-heap with value x )
2) 2 x (a query of this type means to remove an element at position x from the min-heap)
3) 3 (a query like this removes the min element from the min-heap and prints it ).

Example 1:

Input:
Q = 7
Queries:
insertKey(4)
insertKey(2)
extractMin()
insertKey(6)
deleteKey(0)
extractMin()
extractMin()
Output: 2 6 - 1
Explanation: In the first test case for
query 
insertKey(4) the heap will have  {4}  
insertKey(2) the heap will be {2 4}
extractMin() removes min element from 
             heap ie 2 and prints it
             now heap is {4} 
insertKey(6) inserts 6 to heap now heap
             is {4 6}
deleteKey(0) delete element at position 0
             of the heap,now heap is {6}
extractMin() remove min element from heap
             ie 6 and prints it  now the
             heap is empty
extractMin() since the heap is empty thus
             no min element exist so -1
             is printed.

Solution

class MinHeap {
    int[] harr;
    int capacity;
    int heap_size;
    MinHeap(int cap) {
        heap_size = 0;
        capacity = cap;
        harr = new int[cap];
    }
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }

    //Function to extract minimum value in heap and then to store 
    //next minimum value at first index.
    int extractMin()
    {
        if(heap_size==0) return -1;
        // Your code here.
        int min = harr[0];
        swap(harr, 0, heap_size-1);
        heap_size-=1;
        MinHeapify(0);
        return min;
    }

    //Function to insert a value in Heap.
    void insertKey(int k) 
    {
        // Your code here.
        if(heap_size + 1>capacity) return;

        heap_size += 1;
        int index = heap_size-1;

        decreaseKey(index, k);
    }

    //Function to delete a key at ith index.
    void deleteKey(int i) 
    {
        // Your code here.
        if(i>=heap_size) return;

        //We have to keep minimum because 
        //if there is only one element then we cannot swap with last element
        //Then later extract the minimum
        decreaseKey(i, Integer.MIN_VALUE);

        extractMin();
    }

    //Function to change value at ith index and store that value at first index.
    void decreaseKey(int i, int new_val) 
    {
        harr[i] = new_val;
        while (i != 0 && harr[parent(i)] > harr[i]) {
            swap(harr, i, parent(i));
            i = parent(i);
        }
    }

    /* You may call below MinHeapify function in
      above codes. Please do not delete this code
      if you are not writing your own MinHeapify */
    void MinHeapify(int i) {
        int l = left(i);
        int r = right(i);
        int smallest = i;
        if (l < heap_size && harr[l] < harr[i]) smallest = l;
        if (r < heap_size && harr[r] < harr[smallest]) smallest = r;
        if (smallest != i) {
            swap(harr, i, smallest);
            MinHeapify(smallest);
        }
    }

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