Heap in Python using Object-Oriented Programming (OOP) concepts
Do not miss this exclusive book on Binary Tree Problems. Get it now for free.
In this article at OpenGenus, we will implement Heap in Python using Object Oriented Programming.
Table of Contents:
- Introduction
- Implementing a Heap Class
2.1. Initializing the Heap
2.2. Pushing an Item to the Heap
2.3. Popping the Highest-Priority Item from the Heap
2.4. Peeking at the Highest-Priority Item in the Heap
2.5. Checking if the Heap is Empty
2.6. Helper Methods for Maintaining the Heap Property - Using the Heap Class
- Conclusion
1. Introduction
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues, where elements are assigned priorities and the highest-priority element is always at the root of the heap. Python, being a versatile and powerful programming language, provides built-in support for heaps through the heapq module. In this article, we will explore how to implement a heap in Python using object-oriented programming (OOP) concepts.
2. Implementing a Heap Class
Let's start by creating a Heap class that will serve as the blueprint for our heap implementation.
2.1. Initializing the Heap
class Heap:
def __init__(self):
self.heap = []
The __init__ method initializes an empty heap by creating an empty list heap.
2.2. Pushing an Item to the Heap
def push(self, item):
self.heap.append(item)
self._sift_up(len(self.heap) - 1)
The push method adds an item to the heap. It appends the item to the end of the heap list and then calls the _sift_up method to maintain the heap property by swapping the item with its parent until the heap property is satisfied.
2.3. Popping the Highest-Priority Item from the Heap
def pop(self):
if self.is_empty():
raise IndexError("Heap is empty")
self._swap(0, len(self.heap) - 1)
item = self.heap.pop()
self._sift_down(0)
return item
The pop method removes and returns the highest-priority item from the heap. It swaps the root element (index 0) with the last element in the heap list, removes the last element, and then calls the _sift_down method to maintain the heap property by swapping the root element with its largest child until the heap property is satisfied. The _sift_down method is used here to rearrange the heap after popping the highest-priority item.
2.4. Peeking at the Highest-Priority Item in the Heap
def peek(self):
if self.is_empty():
raise IndexError("Heap is empty")
return self.heap[0]
The peek method returns the highest-priority item from the heap without removing it. It simply returns the item at index 0.
2.5. Checking if the Heap is Empty
def is_empty(self):
return len(self.heap) == 0
The is_empty method checks if the heap is empty by checking the length of the heap list.
2.6. Helper Methods for Maintaining the Heap Property
def _sift_up(self, index):
while index > 0:
parent = (index - 1) // 2
if self.heap[index] <= self.heap[parent]:
break
self._swap(index, parent)
index = parent
def _sift_down(self, index):
while index * 2 + 1 < len(self.heap):
left_child = index * 2 + 1
right_child = index * 2 + 2
swap_index = left_child
if right_child < len(self.heap) and self.heap[right_child] > self.heap[left_child]:
swap_index = right_child
if self.heap[index] >= self.heap[swap_index]:
break
self._swap(index, swap_index)
index = swap_index
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
The _sift_up method is a helper method used during the push operation to maintain the heap property. It compares the item at the given index with its parent and swaps them if necessary. The method continues swapping until the item reaches its correct position in the heap.
The _sift_down method is a helper method used during the pop operation to maintain the heap property. It compares the item at the given index with its children and swaps it with the larger child if necessary. The method continues swapping until the item reaches its correct position in the heap.
3. Using the Heap Class
# Create a heap instance
heap = Heap()
# Push elements to the heap
heap.push(10)
heap.push(5)
heap.push(15)
heap.push(8)
# Get the highest-priority item (without removal)
print(heap.peek()) # Output: 15
# Pop the highest-priority item
print(heap.pop()) # Output: 15
# Check if the heap is empty
print(heap.is_empty()) # Output: False
The above code demonstrates the usage of the Heap class. We created a Heap instance and pushed several elements onto the heap. We then demonstrated how to retrieve the highest-priority item using the peek method and how to remove it using the pop method. Finally, we checked if the heap is empty using the is_empty method.
4. Conclusion
In conclusion, implementing a heap in Python using object-oriented programming (OOP) concepts allows us to create a reusable and modular data structure. By encapsulating the heap's logic and operations within a class, we can easily manage the heap's state and behavior. The Heap class we created provides methods for pushing, popping, peeking, and checking the emptiness of the heap, adhering to the heap property throughout these operations.
By understanding and implementing heaps using OOP concepts, you can leverage this powerful data structure in various applications, especially those that involve priority-based operations.
Complete code:
class Heap:
def __init__(self):
self.heap = []
def push(self, item):
self.heap.append(item)
self._sift_up(len(self.heap) - 1)
def pop(self):
if self.is_empty():
raise IndexError("Heap is empty")
self._swap(0, len(self.heap) - 1)
item = self.heap.pop()
self._sift_down(0)
return item
def peek(self):
if self.is_empty():
raise IndexError("Heap is empty")
return self.heap[0]
def is_empty(self):
return len(self.heap) == 0
def _sift_up(self, index
):
while index > 0:
parent = (index - 1) // 2
if self.heap[index] <= self.heap[parent]:
break
self._swap(index, parent)
index = parent
def _sift_down(self, index):
while index * 2 + 1 < len(self.heap):
left_child = index * 2 + 1
right_child = index * 2 + 2
swap_index = left_child
if right_child < len(self.heap) and self.heap[right_child] > self.heap[left_child]:
swap_index = right_child
if self.heap[index] >= self.heap[swap_index]:
break
self._swap(index, swap_index)
index = swap_index
def _swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
Sign up for FREE 3 months of Amazon Music. YOU MUST NOT MISS.