Heap Data Structure-
In data structures,
• Heap is a specialized data structure.
• It has special characteristics.
• A heap may be implemented using a n-ary tree.
Binary Heap-
A binary heap is a Binary Tree with the following two properties-
Ordering Property
• Structural Property
1. Ordering Property-
By this property,
• Elements in the heap tree are arranged in specific order.
• This gives rise to two types of heaps- min heap and max heap.
2. Structural Property-
By this property,
• Binary heap is an almost complete binary tree.
• It has all its levels completely filled except possibly the last level.
• The last level is strictly filled from left to right.
Types of Binary Heap-
Depending on the arrangement of elements, a binary heap may be of following two
types-
1. Max Heap
2. Min Heap
1. Max Heap-
Max Heap conforms to the above properties of heap.
• In max heap, every node contains greater or equal value element than its child
nodes.
• Thus, root node contains the largest value element.
Example-
Consider the following example of max heap-
This is max heap because-
• Every node contains greater or equal value element than its child nodes.
• It is an almost complete binary tree with its last level strictly filled from left to right.
2. Min Heap-
• Min Heap conforms to the above properties of heap.
• In min heap, every node contains lesser value element than its child nodes.
• Thus, root node contains the smallest value element.
Example-
Consider the following example of min heap-
This is min heap because-
• Every node contains lesser value element than its child nodes.
• It is an almost complete binary tree with its last level strictly filled from left to right.
Array Representation of Binary Heap-
A binary heap is typically represented as an array.
For a node present at index ‘i’ of the array Arr-
If indexing starts with 0,
• Its parent node will be present at array location = Arr [ i/2 ]
• Its left child node will be present at array location = Arr [ 2i+1 ]
• Its right child node will be present at array location = Arr [ 2i+2 ]
If indexing starts with 1,
• Its parent node will be present at array location = Arr [ ⌊i/2⌋ ]
• Its left child node will be present at array location = Arr [ 2i ]
• Its right child node will be present at array location = Arr [ 2i+1 ]
Important Notes-
Note-01:
• Level order traversal technique may be used to achieve the array representation
of a heap tree.
• Array representation of a heap never contains any empty indices in between.
• However, array representation of a binary tree may contain some empty indices
in between.
Note-02:
Given an array representation of a binary heap,
• If all the elements are in descending order, then heap is definitely a max heap.
• If all the elements are not in descending order, then it may or may not be a max
heap.
• If all the elements are in ascending order, then heap is definitely a min heap.
• If all the elements are not in ascending order, then it may or may not be a min
heap.
Note-03:
• In max heap, every node contains greater or equal value element than all its
descendants.
• In min heap, every node contains smaller value element that all its descendants.
PRACTICE PROBLEMS BASED ON HEAP DATA
STRUCTURE-
Problems-
Consider a binary max-heap implemented using an array. Which one of the following
array represents a binary max-heap? (GATE CS 2009)
Solutions-
Part-01: 25, 14, 16, 13, 10, 8, 12-
The given array representation may be converted into the following structure-
Clearly,
• It is a complete binary tree.
• Every node contains a greater value element than its child nodes.
Thus, the given array represents a max heap.
Part-02: 25, 12, 16, 13, 10, 8, 14-
The given array representation may be converted into the following structure-
Clearly,
• It is a complete binary tree.
• Every node does not contain a greater value element than its child nodes. (Node
12)
• So, it is not a max heap.
• Every node does not contain a smaller value element than its child nodes.
• So, it is not a min heap.
Thus, the given array does not represents a heap.
Part-03: 25, 14, 12, 13, 10, 8, 16-
The given array representation may be converted into the following structure-
Clearly,
• It is a complete binary tree.
• Every node does not contain a greater value element than its child nodes. (Node
12)
• So, it is not a max heap.
• Every node does not contain a smaller value element than its child nodes.
• So, it is not a min heap.
Thus, the given array does not represents a heap.
Part-04: 25, 14, 13, 16, 10, 8, 12-
The given array representation may be converted into the following structure-
Clearly,
• It is a complete binary tree.
• Every node does not contain a greater value element than its child nodes. (Node
14)
• So, it is not a max heap.
• Every node does not contain a smaller value element than its child nodes.
• So, it is not a min heap.
• Thus, the given array does not represents a heap.
Heap Operations-
The most basic and commonly performed operations on a heap are-
1. Search Operation
2. Insertion Operation
3. Deletion Operation
Here, we will discuss how these operations are performed on a max heap.
Max Heap-
• In max heap, every node contains greater or equal value element than its child
nodes.
• Thus, root node contains the largest value element.
Example-
The following heap is an example of a max heap-
Max Heap Operations-
We will discuss the construction of a max heap and how following operations are
performed on a max heap-
• Finding Maximum Operation
• Insertion Operation
• Deletion Operation
Max Heap Construction-
Given an array of elements, the steps involved in constructing a max heap are-
Step-01:
Convert the given array of elements into an almost complete binary tree.
Step-02:
Ensure that the tree is a max heap.
• Check that every non-leaf node contains a greater or equal value element than its
child nodes.
• If there exists any node that does not satisfies the ordering property of max heap,
swap the elements.
• Start checking from a non-leaf node with the highest index (bottom to top and
right to left).
Finding Maximum Operation-
• In max heap, the root node always contains the maximum value element.
• So, we directly display the root node value as maximum value in max heap.
Insertion Operation-
Insertion Operation is performed to insert an element in the heap tree.
The steps involved in inserting an element are-
Step-01:
Insert the new element as a next leaf node from left to right.
Step-02:
Ensure that the tree remains a max heap.
• Check that every non-leaf node contains a greater or equal value element than its
child nodes.
• If there exists any node that does not satisfies the ordering property of max heap,
swap the elements.
• Start checking from a non-leaf node with the highest index (bottom to top and
right to left).
Deletion Operation-
Deletion Operation is performed to delete a particular element from the heap tree.
When it comes to deleting a node from the heap tree, following two cases are possible-
Case-01: Deletion Of Last Node-
• This case is pretty simple.
• Just remove / disconnect the last leaf node from the heap tree.
Case-02: Deletion Of Some Other Node-
• This case is little bit difficult.
• Deleting a node other than the last node disturbs the heap properties.
The steps involved in deleting such a node are-
Step-01:
• Delete the desired element from the heap tree.
• Pluck the last node and put in place of the deleted node.
Step-02:
Ensure that the tree remains a max heap.
• Check that every non-leaf node contains a greater or equal value element than its
child nodes.
• If there exists any node that does not satisfies the ordering property of max heap,
swap the elements.
• Start checking from a non-leaf node with the highest index (bottom to top and
right to left).
PRACTICE PROBLEMS BASED ON MAX HEAP
OPERATIONS-
Problem-01:
Construct a max heap for the given array of elements-
1, 5, 6, 8, 12, 14, 16
Solution-
Step-01:
We convert the given array of elements into an almost complete binary tree-
Step-02:
• We ensure that the tree is a max heap.
• Node 6 contains greater element in its right child node.
• So, we swap node 6 and node 16.
The resulting tree is-
Step-03:
• Node 5 contains greater element in its right child node.
• So, we swap node 5 and node 12.
The resulting tree is-
Step-04:
• Node 1 contains greater element in its right child node.
• So, we swap node 1 and node 16.
The resulting tree is-
Step-05:
• Node 1 contains greater element in its left child node.
• So, we swap node 1 and node 14.
The resulting tree is-
This is the required max heap for the given array of elements.
Problem-02:
Consider the following max heap-
50, 30, 20, 15, 10, 8, 16
Insert a new node with value 60.
Solution-
Step-01:
We convert the given array of elements into a heap tree-
Step-02:
We insert the new element 60 as a next leaf node from left to right.
The resulting tree is-
Step-03:
• We ensure that the tree is a max heap.
• Node 15 contains greater element in its left child node.
• So, we swap node 15 and node 60.
The resulting tree is-
Step-04:
• Node 30 contains greater element in its left child node.
• So, we swap node 30 and node 60.
The resulting tree is-
Step-05:
• Node 50 contains greater element in its left child node.
• So, we swap node 50 and node 60.
The resulting tree is-
This is the required max heap after inserting the node with value 60.
Problem-03:
Consider the following max heap-
50, 30, 20, 15, 10, 8, 16
Delete a node with value 50.
Solution-
Step-01:
We convert the given array of elements into a heap tree-
Step-02:
• We delete the element 50 which is present at root node.
• We pluck the last node 16 and put in place of the deleted node.
The resulting tree is-
Step-03:
• We ensure that the tree is a max heap.
• Node 16 contains greater element in its left child node.
• So, we swap node 16 and node 30.
The resulting tree is-
This is the required max heap after deleting the node with value 50.
