Understanding of Heap data structure is very important as it is part of many other data structures like priority queue and algorithms like priority queues, Dijkstra’s.

Let’s understand Heap data structure first. Heap is a simple tree based data structure with a unique property that root node is always larger or smaller than its children.

In the current heap we can see parent element is always higher than child nodes, hence it is called max heap. Similarly in case the parent is smaller than children, it will be min heap. Also the heap shown above is binary heap as each parent node has only two child nodes.

Let’s talk about efficiency of the heap data structure in terms of Inserting and deleting the nodes.

Insert a Key: To insert a new node, new element is added to next possible leaf node. It is then compared to its parent node and moved up if larger.

1. Insert node at next leaf

2. While element is less than parent

Swap child and parent

Insert operation in a heap data structure is order of log N, where N is number of nodes available.

Delete Node: Deletion always occur at the root node. Last leaf node is moved to root and then moved down till it is greater than children.

1. Node =root

2. While node <any child

Swap node and largest child

Delete operation in a heap data structure is order of log N, where N is number of nodes available.