Description
Problem description (80 points)
1. Consider the following interfa e for minimum priority queue:
• insert(k,x,&lo ) inserts a key k and element x; The address of a lo ator lo is passed and
updated after insertion.
• min() returns the lo ator to an item (pair – key and element) with the smallest key (but it does
not remove it)
• remove(lo ) removes the item with lo ator lo and updates the minimum priority queue
• isEmpty() tests whether the queue is empty
• de reaseKey(lo , k) updates the minimum priority queue after the key k with lo ator lo was
repla ed
• reatePriorityQueue(file, lo Array) reads (key, element) pairs from the file and initializes
the input array of lo ators lo Array
2. Implement minimum priority queue, on e as an unsorted array or linked list and the other time as a
minimum binary heap.
3. Implement both data stru tures with lo ator pattern to support all the above operations, see the le ture
notes and Chap. 8 for more details about Priority Queues and Adaptable Priority Queues se tion 8.4
p. 357. An illustrated example of heap and lo ators also an be found at le PQ-Example.pdf on
the ourse website.
NOTE: It is important that lo ators are stored “outside” the priority queue (PQ), so later you an
lo ate any item in the PQ from outside the PQ. Therefore, you have to pass the lo ator in to or out of
the PQ fun tions, parti ularly, the fun tions that insert items to the PQ, so the lo ators outside are
asso iated with the items/pairs in the PQ.
Without lo ators, to nd a parti ular element in the PQ, you an only go through all the elements,
whi h takes O(n) time. The lo ators an be stored in any e ient stru ture outside the PQ: randoma ess array, hash table or sear h tree, whi h osts O(1), O(1) and O(log n) to nd a spe i lo ator
using its id (say, ity name or item No.). The sample ode gives you an example of hashing dierent
ities to an array of lo ators.
4. Get the number of omparisons for the remove(lo ) and de reaseKey(lo , k) operations for both
the implementation. For example, for a heap you ount omparisons used to remove the smallest
element and then orre t the heap stru ture.
5. You may de ne your lo ator lass as follows, whi h is onsistent with the ode in the le ture slides.
template