Introduction to Min Heap
If you’re interested in computer science, you’ve probably come across the term “Min Heap.” In this article, we’ll explore what it is, how it works, and its applications. A Min Heap is a complete binary tree that follows a specific rule called the heap property.
The heap property states that each node in a Min Heap has a value that is less than or equal to its two children’s values. If we traverse the entire tree according to the heap property, the root node will always have the minimum value of all the nodes in the tree.
Min Heaps are often used to implement priority queues, which are widely used in computer science and real-world applications like job scheduling and traffic optimization.
Representation of Heap in arrays
In memory, we represent a Min Heap as an array. The root element of the tree is stored in the first index of the array.
Each node’s left child is stored in index i*2, and the right child is stored in index i*2+1 where i is the parent node index in the array. Conversely, the parent node of a node at index i is located at index i/2.
Understanding the functions used in the implementation of Min Heap
Now that we know how a Min Heap is represented in memory, let’s take a look at some of the functions used in its implementation.
Min-Heapify function
The Min-Heapify function is responsible for maintaining the heap property. It takes an input node and recursively checks if its values are less than its descendants.
If not, it swaps the node with its smallest descendant and continues the recursion until the node is at the correct position in the tree. The time complexity of the Min-Heapify function is O(log n), where n is the number of nodes in the tree.
Build-Heap function
The Build-Heap function creates a heap from a list of elements. It’s done by calling the Min-Heapify function on each node in the list. The time complexity of the Build-Heap function is O(n), where n is the number of nodes in the tree.
Heappop function
The Heappop function removes and returns the minimum value from the heap, which is located at the root element. After removing the root element, the function calls the Min-Heapify function on the new root to maintain the heap property. The time complexity of the Heappop function is O(log n), where n is the number of nodes in the tree.
Heappush function
The Heappush function adds a new element to the heap while maintaining the heap property. The new element is added to the bottom right-most position in the tree, and the function compares it to its parents recursively, swapping if necessary.
The time complexity of the Heappush function is O(log n), where n is the number of nodes in the tree.
ExtractMin function
The ExtractMin function is a combination of the Heappop and Heappush functions, removing the root element while simultaneously adding a new element. The time complexity of the ExtractMin function is O(log n), where n is the number of nodes in the tree.
Applications of Min Heap
Min Heaps are mostly used to implement priority queues and find the most priority item in a set of items. They are also useful in sorting algorithms like Heapsort and Dijkstra’s shortest path algorithm, which depends on the heap property to find the shortest path between two points in a graph.
Conclusion
In conclusion, a Min Heap is a complete binary tree that follows the heap property, where each node has a value less than or equal to its descendants. Its representation in memory is an array, where each node’s left and right children are found at indices i*2 and i*2+1, respectively.
The Min-Heapify function is used to maintain the heap property and has a time complexity of O(log n). Other important functions used in its implementation include the Build-Heap, Heappop, Heappush, and ExtractMin functions, each with a time complexity of O(log n).
Min Heaps have a wide range of applications in computer science and are particularly useful in priority queues and sorting algorithms.
Complete Python Implementation of Min Heap Data Structure
In the previous sections of this article, we explored what a Min Heap is, how it’s represented in memory, and the functions used in its implementation. In this section, we will provide a complete Python implementation of the Min Heap data structure.
Defining the min_heap class and constructor
The first step in implementing a Min Heap in Python is defining a class and constructor. The constructor takes an optional argument, size_limit, which limits the maximum number of elements that can be added to the heap.
If none is provided, size_limit is set to None.
class MinHeap:
def __init__(self, size_limit=None):
self.cur_size = 0
self.size_limit = size_limit
self.Heap = []
The cur_size attribute is used to keep track of the current number of elements in the heap.
The size_limit attribute, if provided, limits the maximum number of elements the heap can contain. The Heap attribute will contain the actual heap data structure as a list.
Swapnodes helper function
Before we define the Min-Heapify function, we need a helper function to swap nodes in the heap. The swapnodes function takes two nodes of the heap as arguments and swaps their positions in the heap.
def swapnodes(self, node1, node2):
self.Heap[node1], self.Heap[node2] = self.Heap[node2], self.Heap[node1]
Min-Heapify function
The min_heapify function takes a node in the heap and recursively ensures that the heap property is maintained. If the node is a leaf node, the function does nothing.
If not, it identifies the smaller of the node’s two children and compares their values with the node. If the minimum of the two children is smaller than the node, it swaps the two nodes and recursively calls min_heapify on the new child node.
def min_heapify(self, i):
left_child = 2 * i + 1
right_child = 2 * i + 2
smallest = i
if left_child < self.cur_size and self.Heap[left_child] < self.Heap[smallest]:
smallest = left_child
if right_child < self.cur_size and self.Heap[right_child] < self.Heap[smallest]:
smallest = right_child
if smallest != i:
self.swapnodes(i, smallest)
self.min_heapify(smallest)
Heappush function
The heappush function adds a new element to the heap while maintaining the heap property. It first checks if the heap has reached its maximum size limit (if one was specified).
If the maximum size limit has been reached, the function returns without adding the new element. If the heap has not reached its maximum size limit, the function appends the new element to the end of the heap.
The function then compares the new element with its parent node recursively and swaps the elements if necessary.
def heappush(self, element):
if self.size_limit and self.cur_size >= self.size_limit:
return
self.Heap.append(element)
self.cur_size += 1
i = self.cur_size - 1
while i > 0 and self.Heap[(i - 1) // 2] > self.Heap[i]:
self.swapnodes(i, (i - 1) // 2)
i = (i - 1) // 2
Heappop function
The heappop function removes and returns the minimum value from the heap, which is located at the root element. It first checks if the heap is empty, in which case the function returns None.
If the heap is not empty, the function removes the root element and replaces it with the last element of the heap. The function then calls min_heapify on the new root to maintain the heap property.
def heappop(self):
if not self.cur_size:
return None
if self.cur_size == 1:
self.cur_size -= 1
return self.Heap.pop()
root = self.Heap[0]
self.Heap[0] = self.Heap.pop()
self.cur_size -= 1
self.min_heapify(0)
return root
Build_heap function
The build_heap function takes a list of elements and builds a Min Heap from them. It does this by calling min_heapify on each node in the heap using a for loop.
def build_heap(self, elements):
self.cur_size = len(elements)
self.Heap = elements[:]
for i in range(len(elements) // 2 - 1, -1, -1):
self.min_heapify(i)
Printing Helper function
In order to check the state of the heap at any given time, we can implement the print_heap function to print the contents of the heap.
def print_heap(self):
for i in range(len(self.Heap)):
print(self.Heap[i], end=' ')
print()
Driver Code
Now that we have implemented all the necessary functions for the Min Heap, let's write some driver code that will use the heap. In this example, we will create a Min Heap, add some elements to it, and then remove them in turn.
heap = MinHeap()
heap.heappush(5)
heap.heappush(3)
heap.heappush(6)
heap.heappush(1)
heap.print_heap()
print(heap.heappop())
print(heap.heappop())
print(heap.heappop())
print(heap.heappop())
The output of this code should be:
1 3 6 5
1
3
5
6
Conclusion
In this article, we explored the Min Heap data structure, its representation in memory, and the functions used in its implementation. We then provided a complete Python implementation of the Min Heap, including the min_heapify, heappush, heappop, build_heap, and print_heap functions.
With this implementation, we can use the Min Heap for a variety of applications, including priority queues and sorting algorithms. In this article, we've explored the Min Heap data structure, which is a complete binary tree that follows the heap property, where each node has a value less than or equal to its descendants.
We've also discussed how to represent a Min Heap in memory using arrays, and implementation details of functions such as min_heapify, heappush, heappop, build_heap, and print_heap functions. Finally, we've provided a Python implementation that can be used for a variety of applications, including priority queues and sorting algorithms.
Takeaways include the importance of Min Heap in computer science and real-world applications like job scheduling and traffic optimization, as well as its significance in sorting algorithms and the Dijkstra shortest path algorithm.