Heap Data Structure-
Before you go through this article, make sure that you have gone through the previous article on Heap Data Structure.
We have discussed-
- Heap is a specialized data structure with special properties.
- A binary heap is a binary tree that has ordering and structural properties.
- A heap may be a max heap or a min heap.
In this article, we will discuss about heap operations.
Heap Operations-
The most basic and commonly performed operations on a heap are-
- Search Operation
- Insertion Operation
- 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.
To gain better understanding about Heap Data Structure,
Next Article- Introduction to Hashing
Get more notes and other study material of Data Structures.
Watch video lectures by visiting our YouTube channel LearnVidFun.
