Minimum Binary Heap

This is an easy and small guide to minimum binary heap. This post does not have the entire code mentioned (although there is a link to the code in the end). The motive is to make you familiar with the concepts and the procedure.

It is recommended to try writing the code on your own.

What is a minimum binary heap?
A binary tree which follows:

• Heap property : Every parent node should be smaller than its children.
• Shape property : The binary heap should be a complete binary tree.

What operations can you perform on a minimum binary heap?

• Insert : Insert an element in the minimum binary heap. {O(log(n))}
• Delete : Delete an element from the minimum binary heap. {O(log(n))}
• Extract-min : Extract the minimum element from the minimum binary heap. {O(1)}

 
Cascade up

Cascading up means taking up the inserted element to its correct position such that none of the properties of a minimum binary heap are violated. This is also known as bubble-up, percolate-up, sift-up, trickle-up or heapify-up.

1. If the element is smaller than its parent, swap the parent and the child.
2. Continue the process until the element is placed at right position. 

 Insert

For inserting an element in a minimum binary heap, all you got to do is follow these two rules:

1. Insert the element in the end of the tree.
2. Cascade up the element until it is smaller than its parent.

GIF by: algorithms.tutorialhorizon.com

Cascade down

Cascading down is just the opposite of cascade up. This is also known as bubble-down, percolate-down, sift-down, trickle down or heapify-down.

1. Check which of the children of the element is smaller.
2. If the element is greater than the smaller child, swap the element and the child.
3. Continue the process such that the heap follows the two properties.

 

Delete

For deleting an element from a minimum binary heap:

1. Find out the index 'i' of the element.
2. Swap the element with the last node 'n' in the tree.
3. Delete the last element of the tree.
4. Cascade down the node 'n' (now at index 'i') until it is greater than its children.

 

GIF by: algorithms.tutorialhorizon.com

 

 

Extract-min

 

We're always maintaining the two properties of minimum binary heap at the time of insertion as well as deletion. This leaves us to an O(1) solution for extracting the minimum element of the heap.
Guesses?
Yes! Just return the root of the heap.

But, what if you wish to extract the minimum element one after the other?

1. Save the root of the tree 'r'.
2. Swap the root with the last element of the tree.
3. Delete the last element of the tree.
4. Perform Cascade down on now root.
5. Return 'r'.

Uses

• Implementing priority queue
• Heap Sort
• Implementing Dijkstra's algorithm in O(E*log(V))

That is all about minimum binary heap. Similarly, you can do maximum binary heap.

Looking for the entire code? See here for C++ solution.