Heap Implementation in Data Structure

Heap:

A heap is a complete binary tree and it is implemented in an array as a sequential representation rather than a linked representation. In Data Structure, there are mainly two types of Heap, A heap is called Max Heap or Descending Heap if every node of the heap has a value greater than or equal to the value of every child of that node.

Similarly, a heap says Min Heap or Ascending Heap if every node of the heap has a value less than or equal to the value of every child of that node. In Heap implementation, we try to keep the tree balanced by creating a complete binary tree.

Heap Implementation:

Insertion into a max heap:

M F P B I Q

Step-1: inset node M

Step-2: insert node F

Step-3: insert node P

Step-4: insert node B

Step-5: insert node I

Step-6: insert node Q

Deletion from Heap:

1. Assign the node to some variable ITEM
2. Replace ITEM with the last node L of the tree
3. Reheap

Suppose ITEM=Q, Then replacing node Q with the last node (L=M) we get,

Applications of Heap Data Structure:

• Heap Sort
• Priority queue
• Dijkstra’s Algorithm