Heap Implementation in Data Structure

Heap:

A heap is a complete binary tree and it is implemented in an array as the sequential representation rather than 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

Heap Implementation in Data Structure

Step-2: insert node F

Heap Implementation in Data Structure

Step-3: insert node P

Heap Implementation in Data Structure

Step-4: insert node B

Heap Implementation in Data Structure

Step-5: insert node I

Heap Implementation in Data Structure

Step-6: insert node Q

Heap Implementation

Deletion from Heap:

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

Heap Deletion

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

Deletion from Heap

Applications of Heap Data Structure:

  • Heap Sort
  • Priority queue
  • Dijkstra’s Algorithm