# Binary Min – Max Heap

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

binary tree has two rules –

- Binary Heap has to be complete binary tree at all levels except the last level. This is called
.*shape property* - All nodes are either greater than equal to (
) or less than equal to (*Max-Heap*) to each of its child nodes. This is called*Min-Heap*.*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 atif available.*[2*i]* - Its
**Right Child**is atif available.*[2*i+1]* - Its
**Parent Node**is atif available.*[i/2]*

Heap Majorly has 3 operations –

- Insert Operation
- Delete Operation
- 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
operation(*bubble-up*)*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.

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

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

Hi, I just wanna ask why is there “int size” in constructor. Its never used.

there is a mistake in this code i guess. u are maintaining the variable position as public . but the bubble up takes the same public value of the variable and alters it which will effect our data structure when we try to insert an element into the min or max heap .

The output : 1 3 2 12 8 4 10 16 0 to extract min in loop is not right. It should be Extract Min:

1,2,3,4,7,8,10,12,16,

why the complexity for delete operation would not be O(1) as delete is always performed at root?