Heap — Explained with Examples

A heap is a tree-based data structure satisfying the heap property, used to implement priority queues with efficient min/max extraction.

Heaps are complete binary trees where each parent node is either smaller than its children (min-heap) or larger than its children (max-heap). The root is always the minimum (min-heap) or maximum (max-heap) element. Heapify rearranges nodes to maintain the heap property after insertion or deletion. Building a heap from an unsorted array takes O(n). Insertion and extraction each take O(log n).

Think of a heap like a hospital emergency room triage system. The most critical patient (smallest value in a min-heap, or highest priority) is always treated first. When a new patient arrives, they are placed appropriately, and the triage nurse rearranges the queue to keep the most urgent case at the front.

Heaps are the standard implementation for priority queues. They are also used in heap sort (O(n log n)), Dijkstra’s algorithm, and scheduling systems.

import heapq

# Min-heap (default)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heapq.heappop(heap))  # 1 (smallest)
print(heapq.heappop(heap))  # 3

# Max-heap (simulated with negatives)
max_heap = []
heapq.heappush(max_heap, -5)
heapq.heappush(max_heap, -3)
heapq.heappush(max_heap, -7)
print(-heapq.heappop(max_heap))  # 7 (largest)

# Heapify an existing array
arr = [9, 4, 7, 1, 3, 6]
heapq.heapify(arr)
print(arr)  # [1, 3, 6, 4, 9, 7]

Heaps are not sorted structures — they only guarantee that the root is the extreme element. For full sorted order, use a BST or sort the heap.

Binary Tree, Sorting Algorithms, Binary Search Tree, Priority Queue

Heap Sort