## 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 dene your lo ator lass as follows, whi h is onsistent with the ode in the le ture slides.

template