A binary heap is a complete tree stored in an array. The parent is ≤ its children (min-heap). heappush / heappop are Θ(log n). Find-min is Θ(1).

Goal

Push (km, city) pairs and pop the nearest cities in order.

heapq

import heapq

pq = []
heapq.heappush(pq, (160, "Nakuru"))
heapq.heappush(pq, (480, "Mombasa"))
heapq.heappush(pq, (0, "Nairobi"))
heapq.heappush(pq, (160, "Eldoret"))
while pq:
    print(heapq.heappop(pq))

Smallest km comes out first. Ties break on the city string.

Index math (why it is an array)

heap = [0, 160, 480, 160]
#        Nairobi Nakuru Mombasa Eldoret  (example layout, not a valid heap)

def parent(i):
    return (i - 1) // 2

def left(i):
    return 2 * i + 1

print("parent of 3", parent(3), "left of 0", left(0))

You rarely write this. heapq already does. The analysis is: bubble up/down at most log₂ n levels.

Priority queue ADT

import heapq

class MinPQ:
    def __init__(self):
        self._data = []

    def push(self, item):
        heapq.heappush(self._data, item)

    def pop(self):
        return heapq.heappop(self._data)

    def empty(self):
        return not self._data

pq = MinPQ()
pq.push((2, "Kisumu"))
pq.push((1, "Nairobi"))
print(pq.pop())
print(pq.empty())

Tip

Dijkstra (later) needs “extract the smallest distance”. That is a heap, not a scan of all cities each time (Θ(n) vs Θ(log n)).