Heap

A Heap is a balanced binary tree that satisfies the heap property:
- Max-Heap: A parent's value is always greater than or equal to its children's values.
- Min-Heap: A parent's value is always smaller than or equal to its children's values.

Array Representation

A heap is represented as an array without pointers. For a node at index i:
- Left child: 2*i + 1
- Right child: 2*i + 2
- Parent: (i-1) // 2

# Max-Heap as an array
# Tree:     90
#          /  \
#         80   70
#        / \
#       50  60
heap = [90, 80, 70, 50, 60]

Insert (Heapify Up)

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

    def insert(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

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

Extract (Heapify Down)

    def extract_max(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        max_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)
        return max_val

    def _heapify_down(self, i):
        largest = i
        left = 2 * i + 1
        right = 2 * i + 2

        if left < len(self.heap) and self.heap[left] > self.heap[largest]:
            largest = left
        if right < len(self.heap) and self.heap[right] > self.heap[largest]:
            largest = right

        if largest != i:
            self.heap[i], self.heap[largest] = self.heap[largest], self.heap[i]
            self._heapify_down(largest)

Build Heap

def build_max_heap(arr):
    heap = MaxHeap()
    heap.heap = arr[:]
    for i in range(len(arr) // 2 - 1, -1, -1):
        heap._heapify_down(i)
    return heap

Python heapq (Min-Heap)

import heapq

# Min-Heap
heap = []
heapq.heappush(heap, 30)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heapq.heappop(heap))  # 10 (minimum)

# Max-Heap using negation
max_heap = []
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -10)
print(-heapq.heappop(max_heap))  # 30 (maximum)

# Build a heap from an array
arr = [5, 3, 8, 1, 2]
heapq.heapify(arr)
print(arr)  # [1, 2, 8, 3, 5]

Time Complexity

Use Cases

• Heap Sort: O(n log n) sorting.
• Priority Queue: Access to the highest-priority element.
• Dijkstra: Shortest path using a priority queue.
• Streaming median: Two heaps (max + min).

Heaps are efficient for prioritization. Let's study the Priority Queue, which uses a heap as its implementation.