Python: Heap Implementation

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.