Reading material

If you use the first edition of the textbook, follow the reading material in orange. If you use the second edition, follow the reading material in brown.

(1st) pages 219-230 (Section 6.3.1-6.3.3)

(2nd) pages 301-314 (Section 7.3.1-7.3.4 up to Implementing Heap-Sort In-Place)

Additional material

Proof of Proposition 6.5/Proposition 7.5 in PostScript and PDF

Assume we have the following heap.

Removing the minimal element takes the following steps.

Inserting an element with key 8 takes the following steps.

Implementation of a priority queue with a heap in pseudocode: PostScript and PDF