3. The heap ADT and what Dijkstra needs from it

The abstract data type

A heap is an abstract data type supporting three operations 10:47, 11:11:

Operation	Signature	Semantics
Insert	insert(x)	Adds x; keys are comparable under a total order 11:11
Delete-min	delete-min(H)	Returns the minimum key in H and removes it 11:50
Decrease-key	decrease-key(p, k)	p is a pointer to an item; replaces that item's key with k, which must be at most the item's current key 11:50, 12:33

Dijkstra as the motivating application

• The heap ADT is precisely the abstraction Dijkstra's algorithm needs 12:33.
• Dijkstra's usage pattern: insert every vertex with key ∞ (the source gets 0), then loop over delete-mins; each relax step is a decrease-key 13:25.
• Problem solved: single-source/single-pair shortest paths with non-negative edge weights 13:54.
• Running time in terms of heap costs, with n vertices and m edges 13:54, corrected by a student to put decrease-key on the m term 17:22, 17:45:

O( n · (t_insert + t_delete-min) + m · t_decrease-key )

• This is exactly why constant-time decrease-key matters: the m term dominates in dense graphs 19:34.