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.
[code lang=”java”]
Insert(P)
if size = maxSize
Increase arraySize
size = size +1
H[size] = p
siftUp(size)
[/code]
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.
[code lang=”java”]
siftUp(i)
while i > 1 and H [ parent(i) ] < H [ i ]
swap H [ parent(i) ] and H [ i ]
i = parent(i)
[/code]
RemoveTop
We extract the root element from the array. Place the last element H[size] in the root. Recursively siftDown to satisfy heap property.
[code lang=”java”]
RemoveTop()
result = H [ 0 ]
H [ 0 ] = H [ size ]
size = size – 1
siftDown ( 1 )
return result
[/code]
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
[code lang=”java”]
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 )
[/code]
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
You Might Also Like
Operations on Min Heap | Walmart | Synopsys