Heap in Python using Object-Oriented Programming (OOP) concepts

In this article at OpenGenus, we will implement Heap in Python using Object Oriented Programming.

Table of Contents:

1. Introduction
2. 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
3. Using the Heap Class
4. 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]