Table of Contents

Complete Guide To Heaps

Heaps

A heap is a complete binary tree in which every node key is compared with its children and arranged accordingly. It is also called as a binary heap.
It has two properties :

  • All levels are full, except the last one, which is filled from left to right
  • Every node should have element greater (or smaller) than or equal to all its children nodes. (duplicates are allowed)

The ordering is of two types:

  1. Max heap : A max heap is a complete binary tree in which the key value in each node is greater than or equal to the key values in the child node.
https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589355508/ArticleImages/heap/max_heap_2_vl8qjl.png
  1. Min heap : A min heap is a complete binary tree in which the key value in each node is smaller than or equal to the key values in its child node.

    >

    https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589138489/ArticleImages/heap/min_heap_vyzibu.png

As heap is a complete binary tree, height of the tree will be logN

Array Representation of Heaps

Heaps can be easily represented as an array since it is a complete binary tree.
Array-based representation is space-efficient.

https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589138489/ArticleImages/heap/heap_array_sunwlo.png
https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589148450/ArticleImages/heap/heap_1_cpcflr.png

Operations on Heap

Heapify

The process of creating a heap data structure froma binary tree is known as Heapify.
Min-Heap or a Max-Heap are constructed using this process.

  1. create binary tree from array
  2. Start from the first index of non-leaf node with index n/2-1.
  3. set largest = i
  4. index of :
    [left child] = 2i + 1
    [right child] = 2i + 2.
    If left child is greater than current node (i.e. element at ith index), set index of left child as largest.
    If right child is greater than current node , set index of right child as largest
  5. Swap largest with current element.
  6. Repeat steps 2-6 until the subtrees are also heapified.
https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589380381/ArticleImages/heap/heapify_srdkm8.png
void Heapify(vector<int> &heap, int i)
{
  int size = heap.size();
  int largest = i;
  int l = 2 * i + 1; //left child
  int r = 2 * i + 2; //right child
  if (l < size && heap[l] > heap[largest])
    largest = l;
  if (r < size && heap[r] > heap[largest])
    largest = r;

  if (largest != i)
  {
    swap(&heap[i], &heap[largest]); // perform swapping
    Heapify(heap, largest);
  }
}

Insertion in Heap

Inserting in a Max heap

  1. Create a new node. (If no node present)
  2. If a node is already present, just insert the new node at the end (last node from left to right.)
  3. Heapify

Note :For Min Heap, parent node is always smaller than newNode.

https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589375670/ArticleImages/heap/INsert_HEAP_pnwuwb.png
void insert(vector<int> &heap, int val)
{
  int size = heap.size();
  if (size == 0)
  {
    heap.push_back(val);
  }
  else
  {
    heap.push_back(val);
    for (int i = size/2-1; i >= 0; i--)
    {
      heapify(heap, i);
    }
  }
}

Deletion in Heap

To delete a node in Max heap:

  1. Select value to be removed.
  2. Swap it with the last element.
  3. Remove the last element.
  4. Heapify the tree.

Note : For Min Heap, both child nodes are greater than the current node.

https://res.cloudinary.com/dc0mjpwf8/image/upload/v1589375669/ArticleImages/heap/DELETEPQ_jaj9p2.png
void hDelete(vector<int> &heap, int val)
{
  int size = heap.size();
  int i;
  for (i = 0; i < size; i++)
  {
    if (val == heap[i])
      break;
  }
  swap(&heap[i], &heap[size - 1]);

  heap.pop_back();
  for (int i = size/2-1; i >= 0; i--)
  {
    heapify(heap, i);
  }
}
[gravityforms id="5" description="false" titla="false" ajax="true"]