Algorithm Guidecomplexity: Insert/Delete O(log n)

Heap

A complete binary tree where a parent is always smaller than its children (min-heap), implemented as an array. Because the root is always the minimum, it's the standard implementation of a priority queue and is central to Dijkstra and heap sort.

01Heap

Explore How It Works

Min-heap. A complete binary tree where the parent is always smaller than its children, so the minimum always sits at the root.

push(3) · Add 3 at the end and compare with parent 8. Since 3 < 8, it must sift up.

Swap 3 and 8. 3 rises to the root and takes the minimum's place.

push(5) · Add 5 at the end and compare with parent 3. Since 5 > 3, it stops in place.

push(1) · Add 1 at the end and compare with parent 8. Since 1 < 8, it sifts up.

After swapping 1 and 8, compare with parent 3 again. Since 1 < 3, it sifts up once more.

Swap 1 and 3. 1 has risen all the way to the root.

Done · the root is always the minimum (1). A priority queue uses this property to pull the 'most urgent' item in O(log n).

Live Python

1def heappush(heap, val):

2 heap.append(val) # append at end

3 i = len(heap) - 1

4 while i > 0:

5 parent = (i - 1) // 2

6 if heap[i] < heap[parent]:

7 heap[i], heap[parent] = heap[parent], heap[i]

8 i = parent # up one level

9 else:

10 break # in place

1 / 8

02 Understand It Simply

For Everyone

🔑How It Works

A parent is always greater than or equal to its children, so the largest value can be taken straight off the top without sorting everything.

💡In Plain Words

A tree shape where the parent is always smaller than (or larger than) its children.

The top is always the minimum, so you can pull the 'highest-priority item' instantly.

📍Where It's Used

–Priority queues
–handling urgent tasks first
–Dijkstra shortest paths
–heap sort

03 Python Implementation

A clean, readable reference implementation of the core logic of Heap.

core_implementation.py

import heapq

heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 8)

smallest = heapq.heappop(heap)  # 1

# build heap in one pass (O(n))
data = [5, 1, 8, 3, 2]
heapq.heapify(data)