# 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

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

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 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 .