Get this book -> Problems on Array: For Interviews and Competitive Programming

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]
```