## Binary Heap

A binary heap is a complete binary tree which satisfies the heap ordering property. The ordering can be one of two types:

- Min-heap property: Value of each node is greater than or equal to the value of its parent, with the minimum-value element at the root.
- Max-heap property: Value of each node is less than or equal to the value of its parent, with the maximum-value element at the root.

Min – Max property must be recursively true for all nodes in Binary Tree. Since a heap is a complete binary tree, it has a smallest possible height – a heap with N nodes always has O(log N) height. A heap is useful data structure when you need to remove the object with the highest (or lowest) priority. A common use of a heap is to implement a priority queue.

## Heap Operations

Heap majorly has three operations : –

- Insert Operation
- Delete Operation
- Extract-Min (OR Extract-Max)

### Insert Operation

- Add the element at the bottom leaf of the Heap. Element are added at the bottom to make heap a complete binary tree. If the element are added at the root, heap may not be height balanced.
- Perform the Bubble-Up operation.
- All Insert Operations must perform the bubble-up operation.

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

### 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. Replacing last level so that heap property is intact for all the level above the deleted node.
- Perform Sink-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.

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

## Binary heap implementation

Since the tree is complete, we use the following array implementation. Given array `A`

such that

- A(1) – contains the root
- Node in A(i) has its left child in A(2*i), its right child in A(2*i+1), and its parent in A([i/2]).

The smallest element is always at the root, thus the access time to the element with highest priority is constant O(1).

6 | 10 | 12 | 15 | 17 | 21 | 23 | 20 | 19 | 34 |

The nodes of the tree are written in the array level by level from left to right. The first element in the array is 6 – this is the node at level 0. Then come 10 and 12 – the nodes at level 1.Further we have 15, 17 (children of 10), then 18 and 23 (children of 12) – all at level 2. Finally we have 20, 19 and 34 – the nodes at the last level., this is the element 34.

Code implementation :- min-heap