Reading material

Pages 298-314 (Section 7.2.3-7.3.4 up to Implementing Heap-Sort In-Place), pages 334-337 (Section 8.1.1)

Additional material

Proof of 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

HeapPriorityQueue
PriorityQueueFullException
InPlaceHeapSorter
Dictionary

Question

Given a Dictionary, find the keys which occur more than once in the Dictionary.