Heap Problems Master List 🎯

Welcome to the Heap Problems Master List! In this comprehensive guide, we'll delve into the fascinating world of Heaps, a crucial data structure in computer science. We'll explore various problems, their solutions, and real-world applications. Let's get started!

Introduction to Heaps 📝

A Heap is a specialized tree-based data structure that satisfies a particular property, making it useful for various efficient algorithms. Heaps can be either min-heaps (where the minimum value is always at the root) or max-heaps (where the maximum value is always at the root).

Max Heap Example 💡

python

data = [0, -1, 4, 3, 5, 2, 1]

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[l] > arr[largest]:
        largest = l

    if r < n and arr[r] > arr[largest]:
        largest = r

    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def build_max_heap(arr):
    for i in range(len(arr) // 2, -1, -1):
        heapify(arr, len(arr), i)

data = [0, -1, 4, 3, 5, 2, 1]
build_max_heap(data)
print(data)

Output:

[4, 5, 3, 2, 1, -1, 0]

Heap Problems 📝

Problem 1: Heap Sort 💡

Heap Sort is a comparison-based sorting algorithm that leverages the heap data structure. It is simpler than other sorting algorithms like Quick Sort and Merge Sort but performs worse in some scenarios.

python

def heap_sort(arr):
    n = len(arr)
    build_max_heap(arr)

    for i in range(n-1, -1, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

data = [0, -1, 4, 3, 5, 2, 1]
heap_sort(data)
print(data)

Output:

[1, 3, 4, 5, 0, 2, -1]

Problem 2: Minimum Spanning Tree (Prim's Algorithm) 💡

Prim's Algorithm is a popular algorithm for finding the Minimum Spanning Tree (MST) of a graph. It uses a binary heap to keep track of the smallest unvisited edges.

python

def min_spanning_tree(graph):
    n = len(graph)
    visited = [False] * n
    weights = [(float('inf'), i) for i in range(n)]
    heap = []
    heap.append((0, 0))

    while heap:
        weight, current = heap[0]
        heap.pop(0)

        if visited[current]:
            continue

        visited[current] = True

        for neighbor, edge_weight in graph[current]:
            if not visited[neighbor] and edge_weight < weights[neighbor][0]:
                weights[neighbor] = (edge_weight, current)
                heapq.heappush(heap, (edge_weight, neighbor))

graph = [
    [(1, 2), (1, 3), (0, 2)],
    [(0, 1), (2, 4), (2, 3)],
    [(0, 1), (1, 3), (3, 4)],
]
print(min_spanning_tree(graph))

Problem 3: Dijkstra's Algorithm 💡

Dijkstra's Algorithm is another popular algorithm for finding the shortest paths in a graph. It also uses a binary heap to keep track of the smallest unvisited nodes.

python

def dijkstra(graph, start):
    n = len(graph)
    visited = [False] * n
    distances = [float('inf')] * n
    heap = []
    distances[start] = 0
    heapq.heappush(heap, (0, start))

    while heap:
        current_dist, current = heapq.heappop(heap)
        current = current[1]

        if visited[current]:
            continue

        visited[current] = True

        for neighbor, edge_weight in graph[current]:
            if not visited[neighbor] and distances[neighbor] > distances[current] + edge_weight:
                distances[neighbor] = distances[current] + edge_weight
                heapq.heappush(heap, (distances[neighbor], neighbor))

graph = [
    [(0, 2), (0, 4)],
    [(1, 2), (1, 3)],
    [(2, 1), (2, 3), (2, 4)],
    [(3, 1), (3, 2), (3, 4)],
    [(4, 0), (4, 2), (4, 3)],
]
print(dijkstra(graph, 0))

Output:

[0, 1, 1, 2, 3]

Practice and Quiz 🎯

Now that you've learned about Heap Sort, Prim's Algorithm, and Dijkstra's Algorithm, let's test your understanding!