Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Binary Min — Max Heap

A binary heap is a heap data struc­ture cre­ated using a binary tree.

binary tree has two rules -

  1. Binary Heap has to be com­plete binary tree at all lev­els except the last level. This is called shape prop­erty.
  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 prop­erty.

Imple­men­ta­tion:

  • Use array to store the data.
  • Start stor­ing from index 1, not 0.
  • For any given node at posi­tion i:
  • Its Left Child is at [2*i] if available.
  • Its Right Child is at [2*i+1] if available.
  • Its Par­ent Node is at [i/2]if avail­able.
Max-Heap

Max-Heap

Min-Heap

Min-Heap

 

 

 

 

 

 

 

Heap Majorly has 3 operations -

  1. Insert Oper­a­tion
  2. Delete Oper­a­tion
  3. Extract-Min (OR Extract-Max)

Insert Oper­a­tion:

  • Add the ele­ment at the bot­tom leaf of the Heap.
  • Per­form the Bubble-Up operation.
  • All Insert Oper­a­tions must per­form the bubble-up oper­a­tion(it is also called as up-heap, percolate-up, sift-up, trickle-up, heapify-up, or cascade-up)

Bubble-up Oper­a­tion:

  • If inserted ele­ment is smaller than its par­ent node in case of Min-Heap OR greater than its par­ent node in case of Max-Heap, swap the ele­ment with its parent.
  • Keep repeat­ing the above step, if node reaches its cor­rect posi­tion, STOP.

 

Insert() - Bubble-Up Min-Heap

Insert() — Bubble-Up Min-Heap

Extract-Min OR Extract-Max Operation:

  • Take out the ele­ment from the root.( it will be min­i­mum in case of Min-Heap and max­i­mum in case of Max-Heap).
  • Take out the last ele­ment from the last level from the heap and replace the root with the element.
  • Per­form Sink-Down
  • All delete oper­a­tion must per­form Sink-Down Oper­a­tion ( also known as bubble-down, percolate-down, sift-down, trickle down, heapify-down, cascade-down).

Sink-Down Oper­a­tion:

  • If replaced ele­ment 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 ele­ment with its small­est child(Min-Heap) or with its great­est child(Max-Heap).
  • Keep repeat­ing the above step, if node reaches its cor­rect posi­tion, STOP.
Delete OR Extract Min from Heap

Delete OR Extract Min from Heap

Delete Oper­a­tion:

  • Find the index for the ele­ment to be deleted.
  • Take out the last ele­ment from the last level from the heap and replace the index with this element .
  • Per­form Sink-Down

Time and Space Complexity:

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

 

Com­plete Code for Min-Heap:

Out­put:

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

You may also like...

  • Eugen Daroczy

    You may want to replace lines #35–37 with one call to swap(pos, pos/2);

  • Tomáš Vebr

    Hi, I just wanna ask why is there “int size” in con­struc­tor. Its never used.

  • biswa­jit singh

    there is a mis­take in this code i guess. u are main­tain­ing the vari­able posi­tion as pub­lic . but the bub­ble up takes the same pub­lic value of the vari­able and alters it which will effect our data struc­ture when we try to insert an ele­ment into the min or max heap .