Data Structures and

Algorithms in Python
Michael T. Goodrich
Department of Computer Science
University of California, Irvine

Roberto Tamassia
Department of Computer Science
Brown University

Michael H. Goldwasser
Department of Mathematics and Computer Science
Saint Louis University

Instructor’s Solutions Manual

9 Priority Queues

Hints and Solutions

Reinforcement
R-9.1) Hint Each remove min( ) operation takes O(log n) time.
R-9.2) Hint Observe that the keys are guaranteed to satisfy the heap-order
property. What other property does T need to satisfy in order to be a heap?
R-9.3) Hint Use a simple list-based priority queue and a pencil with a
good eraser.
R-9.3) Solution (1, D), (3, J), (4, B), (5, A), (2, H), (6, L).
R-9.4) Hint There is a very good reason this exercise appears in this chap-
ter.
R-9.4) Solution The best data structure for this air-traffic control simu-
lation is a priority queue. The priority queue will enable the handling of
the time stamps and keep the events in order so that the event with the
smallest time stamp is extracted easily.
R-9.5) Hint Be prepared!
R-9.5) Solution Keep an additional variable that references the current
minimum entry, and update it as necessary after an insertion. This allows
min to run in O(1) time. Note that removeMin will still require O(n) time;
although the current min can be easily found and removed, that method
must look through all remaining elements to identify the new minimum.
R-9.6) Hint Sounds too good to be true.
R-9.6) Solution See previous solution. Also note that if all methods ran
in O(1) time, such a structure could be used to break the lower bound for
sorting (later discussed in Section 12.4.1).
R-9.7) Hint Mimic the illustration style used in the book.
R-9.7) Solution
 53
22 15 36 44 10 3 9 13 29 25
3 15 36 44 10 22 9 13 29 25
3 9 36 44 10 22 15 13 29 25
3 9 10 44 36 22 15 13 29 25
3 9 10 13 36 22 15 44 29 25
3 9 10 13 15 22 36 44 29 25
3 9 10 13 15 22 36 44 29 25
3 9 10 13 15 22 25 44 29 36
3 9 10 13 15 22 25 29 44 36
3 9 10 13 15 22 25 29 36 44
R-9.8) Hint Mimic the illustration style used in the book.
R-9.8) Solution
22 15 36 44 10 3 9 13 29 25
15 22 36 44 10 3 9 13 29 25
15 22 36 44 10 3 9 13 29 25
10 15 22 36 44 3 9 13 29 25
3 10 15 22 36 44 9 13 29 25
3 9 10 15 22 36 44 13 29 25
3 9 10 13 15 22 36 44 29 25
3 9 10 13 15 22 29 36 44 25
3 9 10 13 15 22 25 29 36 44
R-9.9) Hint Think about where insertion-sort has to put each added ele-
ment and design your sequence so that insertion-sort has to put each next
element as far as possible.
R-9.9) Solution A worst-case sequence for insertion-sort would be one
that is in descending order of keys, e.g., 44 36 29 25 22 15 13 10 9 3.
With this sequence, each element will first be moved to the front and then
moved back in the sequence incrementally, as every remaining is pro-
cessed. Thus, each element will be moved n times. For n elements, this
means at a total of n2 times, which implies Ω(n2 ) time overall.
R-9.10) Hint Where might the second smallest key be?
R-9.11) Hint If the smallest is at the top of the heap...
R-9.11) Solution The largest key in a heap may be stored at any external
node.
R-9.12) Hint Consider transforming the keys to invert their order.
R-9.12) Solution Since keys are numeric, we can insert each value with
the negation of its intended key; that way, the maximum original key will
become minimal.
R-9.13) Hint Mimic the illustration style used in the book for insertion-
sort and selection-sort.
54 Chapter 9. Priority Queues
R-9.14) Hint Consider the heap-order property and the definition of the
level number of a node in a tree.
R-9.14) Solution Yes, tree T is a heap. It is a complete binary tree and
each node stores a key value greater than the key of its parent, except for
the root.
R-9.15) Hint Recall the definition of a complete binary tree.
R-9.15) Solution Since a heap is a complete binary tree, the levels of the
heap are filled left to right. Thus, a node with the left child nay not have
the right child. However, if a node has the right child, it must also have
the left child.
R-9.16) Hint The answers are “yes,no,yes.” Now all you have to do is to
give examples for the yeses and a reason for the no.
R-9.16) Solution With a preorder traversal, a heap that produces its entries
in increasing order is that which is represented by the list [1, 2, 5, 3, 4, 6, 7].
There does not exist a heap for which an inorder traversal produces the
keys in order. This is because in a heap the parent is always less than all
of its children or greater than all of its children. The heap represented by
[1, 5, 2, 7, 6, 4, 3] is an example of one which produces its keys in decreas-
ing order during a postorder traversal.
R-9.17) Hint The preorder sequence starts out 0, 1, 3, 7, ...
R-9.18) Hint Consider the last n/2 terms in this sum.
R-9.18) Solution Consider the last n/2 terms in this sum. Each one is
at least log n/2 = log n − 1. Thus, this sum is at least (n/2) log n − n/2,
which is O(n log n).
R-9.19) Hint Try to construct a heap that has larger elements in left sub-
trees.
R-9.19) Solution Imagine the heap which is represented by the array list
[1, 5, 2, 8, 9, 7, 6]. This heap will not produce keys in nondecreasing order
when a preorder traversal is used.
R-9.20) Hint Try to construct a heap that has larger elements in right
subtrees.
R-9.20) Solution Imagine the heap which is represented by the array list
[1, 5, 2, 8, 9, 7, 6]. This heap will not produce keys in nonincreasing order
when a postorder traversal is used.
R-9.21) Hint Mimic the illustration style used in the book.
R-9.22) Hint Mimic the illustration style used in the book.
R-9.23) Hint You need to be very careful about how you partition the keys
between the subtrees rooted at the children of the root.
R-9.24) Hint Structure the insertions so that each requires lots of down-
heap bubbling.
R-9.25) Hint Mimic the illustration style used in the book.
 55

Creativity
C-9.26) Hint Figure out a way to time stamp the entries in the priority
queue.
C-9.26) Solution Maintain a variable m initialized to 0. On a push opera-
tion for element e, call insert(m, e) and decrement m. On a pop operation,
call remove and increment m.
C-9.27) Hint Figure out a way to time stamp the entries in the priority
queue.
C-9.27) Solution Maintain a maxKey variable initialized to 0. On an en-
queue operation for element e, call insertItem(maxKey, e) and increment
maxKey. On a dequeue operation, call removeMinElement.
C-9.28) Hint Is it ever possible that a new element gets a key that is strictly
smaller than a previously inserted element?
C-9.29) Hint Beware: pop(0) is expensive for a Python list.
C-9.30) Hint Use a loop.
C-9.31) Hint Use a loop.
C-9.32) Hint Do simple up-and-down searches in the tree to locate the
last node each time.
C-9.32) Solution
# Utility called just after insert has been called. It updates 'last'
# reference to be an external node of a proper binary tree to expand.
def find insertion position(self):
if self.is empty( ):
z = self.root( );
else:
z = last # assumed reference to current last position
while not self.is root(z) and z == self.right(self.parent(z)):
z = self.parent(z) # walk upward
if not self.is root(z)
z = self.right(self.parent(z)) # then go to right sibling
while not self.is leaf(z) # and finally
z = self.left(z) # find leftmost internal node in subtree
return z # this is the new ``last''
C-9.33) Hint Think about what changes need to be made when leaves are
created or destroyed.
C-9.34) Hint Consider the binary expansion of n − 1, n, and n + 1.
C-9.34) Solution The path to the last node in the heap is given by the
path represented by the binary expansion of n with the highest-order bit
removed.
56 Chapter 9. Priority Queues
C-9.35) Hint Note that the entries do not need to be reported in sorted
order. Use binary recursion on the subtrees of the heap and think about
where the keys smaller than k are stored in the heap T .
C-9.35) Solution If the root of the tree has a key value less than k, record
that value and then recursively search both the left and right subtrees.
This algorithm takes O(k) time, because there is no node in T storing a
key larger than k that has a descendant storing a key less than k.
C-9.36) Hint Think carefully about how location-aware entries can be
implemented efficiently.
C-9.37) Hint Use Calculus.
C-9.37) Solution This summation is relevant because the time for each
upheap call is bounded by O(i) for a node at depth i, and there are at
most 2i nodes at depth i. For an analysis of this series, see solution to
Exercise C-3.39.
C-9.38) Hint Study the combine step in the bottom-up heap construction
algorithm.
C-9.38) Solution Create a new node to serve as rot of T , linked to the
roots of T1 and T2 as its children, and then remove a leaf from one of the
trees and place its item at the new root of T . Then call downheap at that
root to reestablish the heap property.
C-9.39) Hint Make sure you understand the proper semantics when the
parameter is smaller then all heap elements.
C-9.40) Hint Make sure you understand the proper semantics when the
parameter is smaller then all heap elements.
C-9.41) Hint Use a suitably constructed heap.
C-9.41) Solution Build a heap storing the frequent flyers and their mileage,
using bottom-up heap construction. This takes O(n) time. Next, call
removeMin log n times, which takes O(log n · log n) time, to determine
the top log n flyers. Thus, the total time is O(n).
C-9.42) Hint Start by using the bottom-up construction.
C-9.43) Hint Process elements one at a time, always storing the largest k
that you have seen.
C-9.43) Solution Maintain a minimum-oriented heap with maximum size
k. Start by inserting the first k numbers, and from that point on, if the next
number is greater than the smallest number in the heap, then remove the
smallest number and then insert the new number. There will be at most 2n
heap operations, each of which takes O(log k) time since the heap has at
most k entries.
C-9.44) Hint Create a new nested key type that wraps the provided keys
to invert comparisons.
 57
C-9.45) Hint Write a short function that computes the number of 1’s in
the binary expansion of an integer by using the bitwise “and” operation.
C-9.45) Solution
def count bits(k) {
numOnes = 0
tmp = k
while tmp != 0:
bit = tmp & 1
if bit == 1:
numOnes += 1
tmp = tmp >> 1
return numOnes
C-9.46) Hint Rather than using elements as keys in the priority queue, use
the result of the key function for each element.
C-9.47) Hint Partition the array into a sorted part and an unsorted part
and use swaps to move elements around.
C-9.48) Hint Partition the array into a sorted part and an unsorted part
and use swaps to move elements around.
C-9.48) Solution Note well that the insertion sort implementation given
in Code Fragment 5.10 suffices.
C-9.49) Hint Use the right portion of the array to store the heap.
C-9.50) Hint You will need two priority queues.
C-9.51) Hint Use adaptable priority queues.
C-9.52) Hint You will need two data structures that somehow keep “links”
between each other.
C-9.52) Solution Unmonopoly can be played efficiently using two adapt-
able priority queues (with location-aware entries), one keeping track of
the player with minimum amount of money and the other keeping track of
the player with the most. Each turn involves pairing up the minimum and
maximum elements, redistributing their wealth, and then updating their
keys (in both priority queues). These structures allow constant-time pair-
ing of the minimum and maximum elements and fast logarithmic-time
updating of keys.

Projects
P-9.53) Hint Use as large of inputs as you can for experimentation.
P-9.54) Hint Experiment with for which values of k your new implemen-
tation outperforms the original.
58 Chapter 9. Priority Queues
P-9.55) Hint Use a heap for the priority queue.
P-9.56) Hint Study again the bottom-up heap construction algorithm.
P-9.57) Hint Use a heap for the CPU job priority queue.
P-9.58) Hint Decide early how you are going to implement the “pointers”
for your location-aware entries.