Binary Min – Max Heap

A binary heap is a heap data structure created using a binary tree.

binary tree has two rules –

  1. Binary Heap has to be complete binary tree at all levels except the last level. This is called shape property.
  2. All nodes are either greater than equal to (Max-Heap) or less than equal to (Min-Heap) to each of its child nodes. This is called heap property.

Implementation:

  • Use array to store the data.
  • Start storing from index 1, not 0.
  • For any given node at position i:
  • Its Left Child is at [2*i] if available.
  • Its Right Child is at [2*i+1] if available.
  • Its Parent Node is at [i/2]if available.

Max-Heap

Min-Heap

 

 

 

 

 

 

 

Heap Majorly has 3 operations –

  1. Insert Operation
  2. Delete Operation
  3. Extract-Min (OR Extract-Max)

Insert Operation:

  • Add the element at the bottom leaf of the Heap.
  • Perform the Bubble-Up operation.
  • All Insert Operations must perform the bubble-up operation(it is also called as up-heap, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up)

Bubble-up Operation:

  • If inserted element is smaller than its parent node in case of Min-Heap OR greater than its parent node in case of Max-Heap, swap the element with its parent.
  • Keep repeating the above step, if node reaches its correct position, STOP.

 

Insert() - Bubble-Up Min-Heap

Insert() – Bubble-Up Min-Heap

Extract-Min OR Extract-Max Operation:

  • Take out the element from the root.( it will be minimum in case of Min-Heap and maximum in case of Max-Heap).
  • Take out the last element from the last level from the heap and replace the root with the element.
  • Perform Sink-Down
  • All delete operation must perform Sink-Down Operation ( also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down).

Sink-Down Operation:

  • If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
  • Keep repeating the above step, if node reaches its correct position, STOP.
Delete OR Extract Min from Heap

Delete OR Extract Min from Heap

Delete Operation:

  • Find the index for the element to be deleted.
  • Take out the last element from the last level from the heap and replace the index with this element .
  • Perform Sink-Down

Time and Space Complexity:

Space O(n)
Search O(n)
Insert O(log n)
Delete O(log n)

 

Complete Code for Min-Heap:


Output:

Original Array :   3  2  1  7  8  4  10  16  12
Min-Heap :  1 3 2 7 8 4 10 16 12
 1 3 2 12 8 4 10 16 0

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

%d bloggers like this: