How to Implement a Binary Heap in Python
How to Implement a Binary Heap in Python
How to Implement a Binary Heap in Python
What is a binary heap, and how can it be implemented in Python?
solveurit24@gmail.com Changed status to publish February 20, 2025
A binary heap is a complete binary tree where each node’s value is either greater than or equal to (max-heap) or less than or equal to (min-heap) its children’s values. Here’s a simple implementation:
class BinaryHeap:
def __init__(self):
self.heap = []
def heappush(self, value):
self.heap.append(value)
self._bubble_up(len(self.heap)-1)
def heappop(self):
if not self.heap:
return None
value = self.heap[0]
self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
self.heap.pop()
self._bubble_down(0)
return value
def _bubble_up(self, index):
parent = (index - 1) // 2
if parent >= 0 and self.heap[index] < self.heap[parent]:
self.heap[index], self.heap[parent] = self.heap[parent], self.heap[index]
self._bubble_up(parent)
def _bubble_down(self, index):
left = 2 * index + 1
right = 2 * index + 2
smallest = index
if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
smallest = left
if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != index:
self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
self._bubble_down(smallest)solveurit24@gmail.com Changed status to publish February 20, 2025