DSA — Non-Linear DS

Heap (Priority Queue)

Complete binary tree where parent ≥ children. O(log n) insert/extract — the foundation of priority queues and Dijkstra's algorithm.

— min read

O(1)Peek Min/Max

O(log n)Insert

O(log n)Extract

Min& Max Heap

✓PQ / Dijkstra

// HEAP (PRIORITY QUEUE)

Interactive visualization

How It Works

Python Code

Complexity

Quiz

Practice

Array Representation

Node i: left=2i+1, right=2i+2, parent=(i-1)//2.

left=2*i+1, right=2*i+2

Insert

Add to end, bubble up — O(log n).

heapq.heappush(heap, val)

Extract Min

Swap root with last, remove, heapify down — O(log n).

heapq.heappop(heap)

Build Heap

Heapify all nodes bottom-up — O(n) total.

heapq.heapify(arr)

python

import heapq

# Min-heap (Python default)
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 3)
min_v = heapq.heappop(heap)  # → 1

# Max-heap: negate values
heapq.heappush(heap, -val)
max_v = -heapq.heappop(heap)

# Build heap in O(n)
heapq.heapify(arr)

O(1)

Peek Min

Root is always minimum

O(log n)

Insert

Bubble up from leaf

O(log n)

Extract

Heapify down from root

O(n)

Build Heap

Bottom-up is linear

Python's heapq.heappop() returns:

Progress 0 / 5 solved

5 problems · 4 PBC · 1 Startup

#091 Top K Frequent Elements Google, Amazon PBC →

#092 Find Median from Data Stream Amazon, Meta PBC →

#093 Kth Largest Element Adobe, Microsoft PBC →

#094 Merge K Sorted Lists Google, Meta PBC →

#095 Sort Characters by Frequency Cure.fit STARTUP →

← AVL Tree Trie →