DEV Community

Sunbeom Kweon (Ben)
Sunbeom Kweon (Ben)

Posted on

[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;
  }
}
Enter fullscreen mode Exit fullscreen mode

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--;
   }
}
Enter fullscreen mode Exit fullscreen mode

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;

Top comments (0)