Binary Heap

Binary Heap

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

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

   

   Min Heap

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

   

   Max Heap

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 : –

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

Insert Oper­a­tion

1. Add the ele­ment at the bot­tom 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.
2. Per­form the Bubble-Up operation.
3. All Insert Oper­a­tions must per­form the bubble-up oper­a­tion.

Bubble-up Oper­a­tion

1. 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.
2. Keep repeat­ing the above step, if node reaches its cor­rect posi­tion.

Delete Oper­a­tion

1. Find the index for the ele­ment to be deleted.
2. Take out the last ele­ment 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.
3. Per­form Sink-Down

Sink-Down Oper­a­tion

1. 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).
2. Keep repeat­ing the above step, if node reaches its cor­rect posi­tion.

Extract-Min OR Extract-Max Operation

1. 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).
2. Take out the last ele­ment from the last level from the heap and replace the root with the element.
3. Per­form Sink-Down
4. All delete oper­a­tion must per­form Sink-Down Oper­a­tion.

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

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