[Algorithms] 12 - Let's Master Heap

1. Introduction of Heap

• Definition

  • Heap is a complete binary tree that satisfies the heap properties (min or max heap).
  • Max Heap: Every node has greater or equal key(value) to their children.
  • Min Heap: Every node has smaller or equal key(value) to their children.

• Properties

  • Basically heap is an array.
  • Height of any heap will be log(n) only.
  • Left child is at 2*i
  • Right child is at 2*i+1
  • Parent is at i/2

2. Insertion (max heap)

• 1) Insert the element to the end of the array.

• 2) Then swap the element with its parent until the parent is greater or equal to the element
  

void Insert(int arr[], int i){
  while(i > 0 && arr[i/2] < arr[i]){

    // Swapping parent and current  
    swap(arr[i/2], arr[i]);

    // Move on to the next element
    i = i/2;
  }
}

3. Deletion (max heap)

• In heap, deletion means deleting the root node.

• 1) Swap the element with the given index with the last element in the heap.

• 2) Delete the current last element.

• 3) Compare swapped element's children. Swap the element with the greater child (only when any of the children are greater or equal to the element).

• 4) Repeat the process until we find the place where both children are smaller than the element.
  

void deleteRoot(int arr[], int& n)
{
    // Get the last element
    int lastElement = arr[n - 1];

    // Replace root with last element
    arr[0] = lastElement;

    // Decrease size of heap by 1 (element deleted)
    n = n - 1;

    // Start from the bottom
    int i = n;

    // Construct the heap again after the deletion
    while(true){

      // After we proceed the root node, break out of the loop.
      if(i < 0)break;

      // Compare two children and swap
      if(i*2 <= n && arr[i] < arr[i*2]){
        swap(arr[i], arr[i*2]);
      } else if(arr[i] < arr[i*2+1]){
        swap(arr[i], arr[i*2+1]);
      }

      i--;
   }
}

4. Heap Sort

• Use one of properties of deletion.

• Every time we delete an element from the heap, we get an additional empty space at the end of the array.

• We also get the maximum element among the heap.

• Therefore, if we keep inserting those deleted elements to the end of the array, the array will be eventually sorted.

5. Heapify

• Heapify allows you to create a heap within O(N) time complexity. Using insertion method would take O(N*log(N)).

• Heapify starts from the bottom. It repeatedly compares every children of nodes and swap with the parent until it reaches to the root node.

  • Max heap example: swap(arr[i], max(arr[2*i], arr[2*i+1]))
  • Min heap example: swap(arr[i], min(arr[2*i], arr[2*i+1]))

6. How to use Heap in C++

• priority_queue<T> can be used as Max Heap in C++. Max Heap is the default behavior of the library.

  • ex) priority_queue<T> pq;

• priority_queue<T> can be used as Min Heap in C++. You just need to pass some additional arguments to the constructor.

  • ex) priority_queue <T, vector<T>, greater<T> > pq;