Description
Problem des
ription (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
lass Item {
private:
int key;
ElemType elem;
Lo
ator
; // a pointer to the
orresonding lo
ator
publi
:
2
Item(
onst int k=0,
onst ElemType& e=ElemType(), Lo
ator
key(k), elem(e), lo
(l) { } //
onstru
tor
};
template
lass Lo
ator {
private:
Item
orresonding item in the PQ
// if the PQ is implemented with an array or list
// int indexItem; // Alternative way: the index of the item in the PQ
// if the PQ is implemented with an array or ve
tor
Lo
ator( Item
};
6. You are provided with a sample test program Main.
pp. In the main(), a minimum priority queue
and an array of lo
ators are
reated.
PriorityQueue
Lo
ator
Array[26℄; // Assume there are at most 26 (key,element) pairs
A test le is provided whi
h
ontains key-element integer pairs. They represent distan
es and number
of stops from the BWI airport to the nine airports, from the textbook gure 13.15(g) at p.642.
//key (distan
e), element (stops) to the
ity
2467 -1 // SFO
3288 -1 // LAX
621 0 // ORD
1423 -1 // DFW
84 0 // JFK
371 1 // BOS
328 1 // PVD
0 0 // BWI
946 0 // MIA
The main()
reates a minimum priority queue from the data and performs a sort based on distan
e
by removing minimum. Next, the main() lls the minimum priority queue again with the same data
by insertion. Lo
ators are spe
ially stored, i.e. the initial letter of a
ity
is hashed to a spot in the
lo
ator array using arrayIndex =
-‘A’. Thus, a
ity
an be lo
ated in
onstant O(1) time in the
lo
ator array and in the priority queue. Then, its key
an be repla
ed in the priority queue.
NOTE: You will have to adapt the Main.
pp to your program.
Report (20 points)
In addition to the regular programming assignment, your report should in
lude answers to the following
problems:
• Des
ribe your algorithms for remove(lo
), de
reaseKey(lo
, k) and
reatePriorityQueue(file,
lo
Array)
• Dis
uss about number of
omparisons for remove(lo
) and de
reaseKey(lo
, k)
• Provide running time of Priority-Queue ADT for both the representations (unsorted array/linked list
and binary heap) express in terms of the big-O notation.
• Compare the running time for the same operations in both the implementations of Priority-Queue
ADT.
3
• Does using the lo
ator pattern have an impa
t on the
omplexity of the priority queue operations for
the both representations?
• Write about three real-life appli
ations where you
an use a minimum priority queue.
4
