Heap

A heap is a specialized tree-based data structure that satisfies the heap property:

Min Heap: The key at the root must be the minimum among all keys present in the heap. The same property must be recursively true for all subtrees.
Max Heap: The key at the root must be the maximum among all keys present in the heap.

Heaps are commonly used to implement priority queues because they allow for efficient retrieval and modification of the highest (or lowest) priority element.

Properties of Heaps

Complete Binary Tree: All levels are fully filled except possibly the last level, which is filled from left to right.
Heap Order Property: Parent node is always greater than (max heap) or less than (min heap) its child nodes.

Visualization of a Min Heap:

Why Do We Need Heaps?

Heaps provide several advantages:

Efficient Priority Queue Implementation: Quick access to the highest or lowest priority element.
Optimal Time Complexities:
- Insertion: O(log n)
- Deletion of Min/Max: O(log n)
- Access Min/Max: O(1)
Memory Efficiency: Can be implemented using arrays without the need for pointers.

Problems Solved by Heaps

Heaps are used in various scenarios:

Scheduling Tasks: Managing tasks based on priority.
Graph Algorithms: Finding the shortest path (Dijkstra’s algorithm) or minimum spanning tree (Prim’s algorithm).
Order Statistics: Finding the k-th smallest or largest element.
Real-Time Systems: Where tasks must be processed in a specific order.

Using the `heapq` Module

Creating a Min Heap:

import heapq

# Initialize an empty list to represent the heap
heap = []

# Add elements to the heap
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 15)
heapq.heappush(heap, 1)

print("Min Heap:", heap)

Min Heap: [1, 5, 15, 10]

min_element = heap[0]
print("Minimum element:", min_element)

Minimum element: 1

min_element = heapq.heappop(heap)
print("Removed element:", min_element)
print("Heap after removal:", heap)

Removed element: 1
Heap after removal: [5, 10, 15]

numbers = [20, 1, 15, 5, 10]
heapq.heapify(numbers)
print("Heapified list:", numbers)

Heapified list: [1, 5, 15, 20, 10]

Implementing a Max Heap

Since heapq only provides a min heap, you can create a max heap by storing elements as negatives.

Creating a Max Heap:

max_heap = []
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -15)
heapq.heappush(max_heap, -1)

# To get the maximum element
max_element = -heapq.heappop(max_heap)
print("Maximum element:", max_element)

Maximum element: 15

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, key):
        # Insert key into the heap
        self.heap.append(key)
        self._sift_up(len(self.heap) - 1)

    def extract_max(self):
        if not self.heap:
            return None
        # Swap the first and last items
        self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
        max_item = self.heap.pop()
        self._sift_down(0)
        return max_item

    def _sift_up(self, idx):
        parent = (idx - 1) // 2
        if idx > 0 and self.heap[parent] < self.heap[idx]:
            self.heap[parent], self.heap[idx] = self.heap[idx], self.heap[parent]
            self._sift_up(parent)

    def _sift_down(self, idx):
        largest = idx
        left = 2 * idx + 1
        right = 2 * idx + 2
        n = len(self.heap)

        if left < n and self.heap[left] > self.heap[largest]:
            largest = left

        if right < n and self.heap[right] > self.heap[largest]:
            largest = right

        if largest != idx:
            self.heap[largest], self.heap[idx] = self.heap[idx], self.heap[largest]
            self._sift_down(largest)

# Usage
max_heap = MaxHeap()
max_heap.insert(10)
max_heap.insert(5)
max_heap.insert(15)
max_heap.insert(1)

print("Max Heap:", max_heap.heap)
print("Extracted Max:", max_heap.extract_max())
print("Heap after extraction:", max_heap.heap)

Max Heap: [15, 5, 10, 1]
Extracted Max: 15
Heap after extraction: [10, 5, 1]

class MinHeap:
    def __init__(self):
        self.heap = []

    def push(self, val):
        heapq.heappush(self.heap, val)

    def pop(self):
        return heapq.heappop(self.heap)

    def peek(self):
        if self.heap:
            return self.heap[0]
        return None

    def __len__(self):
        return len(self.heap)

# Usage example
custom_heap = MinHeap()
custom_heap.push(10)
custom_heap.push(5)
custom_heap.push(30)

print("Peek:", custom_heap.peek())  # Output: 5
print("Popped Element:", custom_heap.pop())  # Output: 5

Peek: 5
Popped Element: 5

Applications of Heaps

Priority Queues

Heaps are perfect for implementing priority queues where elements are processed based on priority.

import heapq

tasks = []
heapq.heappush(tasks, (2, 'Write code'))
heapq.heappush(tasks, (1, 'Debug code'))
heapq.heappush(tasks, (3, 'Test code'))

while tasks:
    priority, task = heapq.heappop(tasks)
    print(f"Processing task: {task} with priority {priority}")

Processing task: Debug code with priority 1
Processing task: Write code with priority 2
Processing task: Test code with priority 3

Heapsort Algorithm

Heapsort leverages the heap data structure to sort elements efficiently.

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    sorted_list = [heapq.heappop(h) for _ in range(len(h))]
    return sorted_list

numbers = [20, 1, 15, 5, 10]
print("Sorted numbers:", heapsort(numbers))

Sorted numbers: [1, 5, 10, 15, 20]

Graph Algorithms

Heaps are used in algorithms like Dijkstra’s to efficiently select the next node with the smallest distance.

Simplified Dijkstra’s Algorithm:

import heapq

def dijkstra(graph, start):
    heap = [(0, start)]
    distances = {vertex: float('inf') for vertex in graph}
    distances[start] = 0

    while heap:
        current_distance, current_vertex = heapq.heappop(heap)

        if current_distance > distances[current_vertex]:
            continue

        for neighbor, weight in graph[current_vertex]:
            distance = current_distance + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(heap, (distance, neighbor))

    return distances

# Graph represented as an adjacency list
graph = {
    'A': [('B', 1), ('C', 4)],
    'B': [('C', 2), ('D', 5)],
    'C': [('D', 1)],
    'D': []
}

print("Shortest distances:", dijkstra(graph, 'A'))

Shortest distances: {'A': 0, 'B': 1, 'C': 3, 'D': 4}

Conclusion

Heaps are a fundamental data structure that provides efficient implementations for priority-based data management. They are critical in various algorithms and real-world applications, especially where performance and efficiency are paramount.

Key Points:

Heaps can be efficiently implemented using arrays.
The heapq module simplifies heap operations in Python.
Heaps are integral in implementing priority queues, sorting algorithms, and graph traversal algorithms.

Understanding heaps will not only prepare you for technical interviews but also enhance your problem-solving skills in algorithm design and optimization.

Practice Problems

Find the K Smallest Elements in an Array

Given an unsorted array and a number k, find the k smallest elements.

Hint: Use a max heap of size k to keep track of the smallest elements.
Merge K Sorted Lists

Given k sorted linked lists, merge them into a single sorted list.

Hint: Use a min heap to efficiently select the smallest head among the lists.
Top K Frequent Elements

Given a non-empty array of integers, return the k most frequent elements.

Hint: Use a heap to keep track of frequencies.
Median in a Stream

Design a data structure that supports adding numbers and finding the median in constant time.

Hint: Use two heaps, a max heap, and a min heap.