Python: Heap Implementation

📘 Premium Read: Access my best content on Medium member-only articles — deep dives into Java, Spring Boot, Microservices, backend architecture, interview preparation, career advice, and industry-standard best practices.

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (176K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

A heap is a specialized tree-based data structure that satisfies the heap property. In a min-heap, for any given node I, the value of I is less than or equal to the values of its children. It's often used in algorithms like Dijkstra's and in data structures like priority queues.

2. Program Overview

In this program, we will:

1. Implement a basic min-heap from scratch.

2. Provide methods to insert a value, delete the minimum value, and peek the minimum value.

3. Code Program

class MinHeap: def __init__(self): # Initialize the heap with a dummy element at index 0 self.heap = [0] self.size = 0 def floatUp(self, index): # Ensure the element at index maintains the heap property while index // 2 > 0: if self.heap[index] < self.heap[index // 2]: # Compare with parent self.heap[index], self.heap[index // 2] = self.heap[index // 2], self.heap[index] index //= 2 def insert(self, value): # Insert a value and maintain the heap property self.heap.append(value) self.size += 1 self.floatUp(self.size) def sinkDown(self, index): # Ensure the element at index maintains the heap property while (index * 2) <= self.size: mc = self.minChild(index) if self.heap[index] > self.heap[mc]: self.heap[index], self.heap[mc] = self.heap[mc], self.heap[index] index = mc def minChild(self, index): # Return the index of the smallest child if (index * 2) + 1 > self.size: return index * 2 else: if self.heap[index * 2] < self.heap[index * 2 + 1]: return index * 2 else: return index * 2 + 1 def popMin(self): # Remove and return the smallest element retval = self.heap[1] self.heap[1] = self.heap[self.size] self.size -= 1 self.heap.pop() self.sinkDown(1) return retval # Test the MinHeap class heap = MinHeap() heap.insert(5) heap.insert(7) heap.insert(3) heap.insert(11) print("Smallest value:", heap.popMin()) print("Next smallest value:", heap.popMin()) 

Output:

Smallest value: 3 Next smallest value: 5 

4. Step By Step Explanation

1. The MinHeap class begins with a dummy element at index 0. This is useful for easier indexing of parent-child relationships.

2. The floatUp method ensures that the newly added element maintains the min-heap property by comparing it with its parent.

3. The sinkDown method ensures that the root element maintains the min-heap property by comparing it with its smallest child.

4. The minChild method returns the index of the smallest child of a given element.

5. The popMin method removes the smallest element (root) and ensures that the new root maintains the heap property.

In the test case, we insert four values and then retrieve the smallest two. As expected, the heap returns the smallest values in order.