Insertion and Deletion in Heaps

In the previous article, we learned about the AVL Tree in Data Structures, In this article, we will learn about the Heap in Data Structures.

78

What is a Heap?

A heap is a tree-based data structure. A binary tree is said to follow the heap data structure if –

  • It is a complete binary tree in which the elements are stored in an array as a sequential representation.
  • All nodes in the tree are greater than their children or vice versa. Therefore, the largest element is at the root and both its children are smaller than the root, and so on. Such a heap is called a max heap. If all nodes are smaller than their children then it is called a min-heap.

In a sequential representation of a complete binary tree, the first item of the array is the root. The left child and the right child of any node are a[k] and a[2k+1] and a[2k+2].

Types of Heap in Data Structures

There are two types of the heap

What is Max Heap?

In the Max heap, the parent nodes must be greater than their child nodes. The same property must be recursively true for all sub-trees in that Binary Tree. In the below diagram, the root node’s value is 100 which is the greatest among all other children nodes. If we sub-divide this binary tree then 60 is greater than 35, 45, and 39, same with another sub tree 43 is greater than 41 and 40.

max heap tree diagram in data structures
max heap tree diagram in data structures

What is Min Heap?

In the Min heap, the key present at the root node must have the smallest or equal value as compared to the other children nodes. The same property must be recursively true for all sub-trees in that Binary Tree.  In the below diagram, the root node’s value is 10 which is the smallest among all other children nodes. If we subdivide this tree then 60 is the smallest with 85, 65, 75 and 93, same with another sub-tree 43 is the smallest with 51 and 50.

min heap tree diagram in data structures
min heap tree diagram in data structures

Insertion and Deletion in a Heap

Now, we will see the insertion and deletion in a Heap –

Deletion in a Heap

  • Replace the root or element to be deleted by the last element.
  • Delete the last element from the Heap.
  • Since the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of the root.

Note – We will consider these operations for max-heap as it is widely used in programming. A similar can be done for min-heap also.

Pseudo-code for this deletion in Heap

The pseudo-code for this deletion is given below –

delete(heap, n):

Begin

if heap is empty, then exit

else

item := heap[1]

last := heap[n]

n := n – 1

for i := 1, j := 2, j <= n, set i := j and j := j * 2, do

if j < n, then

if heap[j] < heap[j + 1], then j := j + 1

end if

if last >= heap[j], then break

heap[i] := heap[j]

done

end if

heap[i] := last

End

 

Now, we will learn about the insertion operation in a heap –

Insertion in a Heap

A node in a max heap is inserted as –

  • Add the element at the end of the array
  • Move that element until it reaches the appropriate position

Pseudo code for insertion in Heap

The pseudo-code for this insertion operation is given below-

insert(heap, n, item):

Begin

if heap is full, then exit

else

n := n + 1

for i := n, i > 1, set i := i / 2 in each iteration, do

if item <= heap[i/2], then break

heap[i] = heap[i/2]

done

end if

heap[i] := item

End

So, in this tutorial, we learned about the heap data structure and the insertion and deletion operations that are performed on it.

Try Free Data Structures MCQ Test

LEAVE A REPLY

Please enter your comment!
Please enter your name here

This site uses Akismet to reduce spam. Learn how your comment data is processed.