Implementation of Basic Min Heap Operations in C++
Following are some the basic operations of min heap that are required to manipulate it’s elements:
Operation Name | Description | Time Complexity | Space Complexity |
|---|---|---|---|
Heapify | Rearranges the position of elements to ensure that the min heap property is maintained. | O(log n) | O(log n) |
Build Heap | Builds a min heap from a given array. | O(n) | O(log n) |
Insert Node | Inserts a new node into the min heap. | O(log n) | O(1) |
Delete Node | Deletes a specific node from the min heap and ensures that the min heap property is maintained after deletion. | O(log n) | O(log n) |
Peek | Returns the topmost element of the min heap. | O(1) | O(1) |
ExtactMin | Removes the root node of the min heap and heapifies the remaining heap. | O(log n) | O(log n) |
Implementation of Heapify Function
- Determine the left and right children using the formulas 2*i+1 and 2*i+2.
- Find the smallest value among the current node, the left child, and the right child.
- If the current node is not the smallest, swap it with the smallest child.
- Recursively apply heapify to the affected subtree to maintain the heap property.
- Continue this process until the heap property is satisified.
Implementation of Build Heap Function
- Start with the last non-leaf node (i.e. size/2 – 1)and move upward to the root node.
- Apply heapify to each node to ensure it satisfies the heap property.
- Continue this process for all nodes up to the root.
- Complete the process when the entire heap conforms to the min heap structure.
Implementation of Insert Node Function
- Increase the heap size by 1.
- Place the new node at the end of the array.
- Set i to the index of the newly added node.
- While i is not the root and the new node’s value is less than its parent’s value:
- Swap the new node with its parent.
- Update i to the index of the parent.
Implementation of Delete Node Function
- Locate the node you wish to remove by traversing the heap.
- Record the index of this node.
- Replace the target node with the last node in the heap.
- Reduce the heap size by 1.
- Apply the heapify function to the index where the node was removed to restore the min heap property.
Implementation of Peek Function
- Check if the heap is empty.
- If the heap is not empty, return the root element (the smallest element in a min heap).
- If the heap is empty, return -1.
Implementation of ExtractMin Function
- Verify if the heap is empty. If it is, return -1.
- Save the root element.
- Replace the root element with the last element in the heap.
- Decrease the heap size by 1.
- Call heapify on the root to restore the min heap property.
- Return the original root element.
Min Heap in C++
A min-heap is a complete binary tree in which the value of each node is less than the value of its left child and right child. This property is true for every node in the tree. In this article, we will learn how we can implement the min heap data structure in C++.