Everything about Heap Data Structure

Article Contents

What is Heap?
Heap Applications
Max Heap Pseudo code
When should you use Heap? ( Timecomplexity and comparision with other methods )

What is Heap?

Heap is a tree-based data structure that is a Complete tree. In the Complete tree, all the levels are completely filled except the last level. It is filled from left to right and usually implemented using a Binary Complete tree. Example of Heap given below

There are two types of Heap,

Min-Heap – Smallest element stored at the root
Max-Heap – Largest element stored at root.

Heap is usually computed on the fly from the array. For an array with 0-based indexing, nodes can be computed based on the below formulas,

Parent(i) => ( i-1 ) / 2

LeftChild(i) => 2i + 1

RightChild(i) => 2i + 2

Note: These formula change for 1-based indexing

For example, if i = 1 Root = 0, RightChild = 3 (2*1+1) , LeftChild = 4 ( 2*1 + 2 )

What is Heapify – Process of converting array into heap is called Heapify

Heap Property:

For Min-Heap, Root must be smaller than its both the children Same applies for all the roots in each sub-tree. Likewise for Max-Heap, root must be greater than its both the children.

Heap Applications

Priority Queue internally uses Binary Heap Data Structure. Priority Queue is used when we need to retreive min/max from bunch of elements. For Example, CPU uses priority queue to get the high priority task from the bunch of tasks.
HeapSort also uses Heap for sorting. It is in-place sorting. We create a Heap from the unsorted array. We get the elements in sorted order.

Max Heap Pseudo Code

Insert

Place the new element at the end of the array. Sift-up elements recursively.


Insert(P)

   if size = maxSize

      Increase arraySize

   size = size +1

   H[size] = p

   siftUp(size)

SiftUp

In SiftUp we compare the child with its parent node. If parent lesser than child, swap elements. Repeat the same in all the levels.


siftUp(i)

while i > 1 and H [ parent(i) ] < H [ i ]

     swap H [ parent(i) ] and H [ i ]

     i = parent(i)

RemoveTop

We extract the root element from the array. Place the last element H[size] in the root. Recursively siftDown to satisfy heap property.


RemoveTop()

      result = H [ 0 ]

      H [ 0 ] = H [ size ]

      size = size - 1

      siftDown ( 1 )

      return result

SiftDown

Check the root with its children. Find the largest child and compare that with root. If root is smaller swap. Recursively check and siftDown


SiftDown ( i)

    maxIndex = i
 
    left = leftChild ( i )

    right = rightChild ( i )

   if left  <= size and H [ left ] > H [ maxIndex ]

      maxIndex = left

   if  right <= size and H [ right ] > H [ maxIndex ]

      maxIndex = right

   if i not equal maxIndex

      swap H [ i ] and H [ maxIndex ]

      siftDown ( maxIndex )

When to use Heap Data Strucuture

Largest among all

Use Heap if you need only largest or smallest element from bunch of elements. Complexity to remove from top is O (1) Cost of maintaining the sorted array and finding the largest is very high compared to Heap.

Faster insert and delete

In Heap both insert and delete takes O ( log n). If we need faster insert and delete, we can use heap. You can ask why not array or linkedlist. In sorted array delete takes O(n) as the elements need to shifted to fill up the space. In Sorted LinkedList, insert takes O ( n ) as we need to compare each element to find a place for the new element. If we use sorted array, every time a element is inserted we need to shift n elements. So Time complexity is O(n). In Heap insertion takes O ( log n ) .

Note : If our goal is to get a complete sorted array after all the insertion, we should use quick sort.

Reference

Data Structure , University of California San Diego, Coursera
Abdul Bari, Youtube

Operations on Min Heap | Walmart | Synopsys

DataStructure Heap