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.
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.
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.
