In this blog post, we’ll explore the intricacies of heap data structures, specifically focusing on minimum heaps. By the end of this article, you’ll have a solid understanding of how this data structure operates, how it is presented as a complete binary tree, and the computational efficiency of the supported operations.
What are Minimum and Maximum Heaps?
Heap data structures are highly efficient for managing a prioritized queue of elements where the order is based on the element’s key value. They come in two flavors: minimum and maximum heaps.
In a minimum heap, the smallest key is always at the top, making it perfect for operations that need to repeatedly access or remove the smallest element. Conversely, a maximum heap keeps the largest key at the top, serving the opposite purpose.
For the purpose of this article, we’ll concentrate on the minimum variation. Understanding this will provide you with the foundation to easily grasp the maximum variation since the concepts are similar, just mirrored.
The Complete Binary Tree Representation
A fundamental concept to understand when discussing the heap data structure is the complete binary tree. This tree-based structure is a tree that is completely filled on all levels, except possibly the last level, which should be filled from left to right. In a general case, there is no requirement on the order of the nodes in the complete binary tree, apart from the structure of the tree itself. However, in the context of a heap, things are different.
In a minimum heap represented as a complete binary tree, every parent node has a value less than or equal to its child nodes. This property must be true for every node in the complete tree.
As an implementation, we usually represent the complete tree as an array. The complete filling of the tree allows the data to be stored compactly in an array, where the position of each element in the array corresponds to a specific level and position in the tree:
- The root element is at index 0.
- For any element at index
i, its children are at indices2*i + 1(left) and2*i + 2(right). - The parent of any element at index
iis at index(i-1)//2.
For example, the above tree would be implemented as the following array – notice the elements are ordered level by level.
Supported Operations
Sift Operations (Internal Operations)
Sift Down
The Sift Down operation is used during the deletion of the root element and the MakeHeap process. It ensures that the correct order is not violated after an element is removed from the root or during the construction of the data structure. Here’s how it works:
- Starting Position: Begin at a specified node.
- Child Comparison: Compare the current node with its children. If either child is smaller than the current node, proceed to the next step.
- Swap and Continue: Swap the current node with the smallest of its children. Then, move down to this child and repeat the comparison process.
- Termination: This process continues until the current node is smaller than both its children or it has no children.
This video is an example of how Sift Down would look like: (Note this is not a valid heap)
Complexity: O(logn) – The operation may require traversing the height of the tree, which is logarithmic relative to the number of elements.
Sift Up
Conversely, the Sift Up operation is used primarily when a new element is inserted at the heap’s end or when an element’s priority is decreased. It adjusts the complete binary tree by moving the new or updated element upward until the heap property is restored. The steps include:
- Starting Position: Begin at a specified node.
- Parent Comparison: Compare the current node with its parent. If the current node is smaller, proceed to the next step.
- Swap and Continue: Swap the current node with its parent and move up to the parent’s position.
- Termination: Repeat the comparison and swapping until the current node is in a position where the heap property is no longer violated or it becomes the root node.
This video is an example of how Sift Up would look like: (Note this is not a valid heap)
Complexity: O(logn) – The operation may require traversing the height of the tree, which is logarithmic relative to the number of elements.
MakeHeap: Building a Heap Efficiently
The MakeHeap operation transforms an unordered array of n elements into a valid heap. This is primarily done by repeatedly using the Sift Down technique, which adjusts elements to ensure the a correct order. Starting from the last non-leaf node all the way up to the root, Sift Down is applied to each element to ensure it is positioned correctly. The operation terminates after applying Sift Down to all these elements.
Complexity: The time complexity of the operation is O(n), where n is the number of elements.
Inserting a new Element
Inserting a new element involves adding the element at the end of the complete tree (maintaining the complete tree property) and then applying a Sift Up operation on the new node. The Sift Up adjusts the added element upward as necessary to maintain the correct order.
Complexity: The insertion operation has a time complexity of O(logn), due to the need to potentially traverse the tree’s height to reposition the new element.
Deleting the Minimum Element
The minimum element is always at the root. To remove it, replace the root with the last element in the complete tree, and then perform a Sift Down operation from the new root to maintain the correct order.
Complexity: Like insertion, deletion has a time complexity of O(logn).
Getting the Minimum Element
This operation is straightforward, as the smallest element is always at the root / the first element in the array.
Complexity: Fetching the minimum element has a time complexity of O(1).
Decrease Key
The Decrease Key operation involves decreasing the value of one element in the data. This may disrupt the heap order, specifically if the new value is smaller than the parent’s value, necessitating a Sift Up on the decreased node to restore order.
Complexity: This operation also runs in O(logn) time, due to the potential shifting required up the tree.
Summary Table
| Operation | Description | Time Complexity |
|---|---|---|
| MakeHeap | Transforms an unordered array into a minimum heap. | O(n) |
| Insert | Adds a new element to the heap, ensuring the correct order is maintained. | O(logn) |
| Remove Minimum | Removes the minimum element (the root), then restructures to maintain the correct order. | O(logn) |
| Get Minimum | Retrieves the minimum element without removing it (found at the root). | O(1) |
| Decrease Key | Decreases the value of a given element, then adjusts the order to maintain the correct order if necessary. | O(logn) |