Table of Contents#### Download Safari Books Online apps: Apple iOS | Android | BlackBerry

### 8.5. Exercises

#### 8.5.1. Reinforcement

Entire Site

Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

For help with exercises, please visit the web site, www.wiley.com/college/goodrich.

R-8.1 What are the running times of each of the functions of the (standard) priority queue ADT if we implement it by adapting the STL

priority_queue?R-8.2 How long would it take to remove the ⌈logn⌉ smallest elements from a heap that contains n entries using the

removeMin()operation?R-8.3 Show that, given only the less-than operator (

<) and the boolean operators and (&&), or (||), and not (!), it is possible to implement all of the other comparators:>, <=, >=, ==, !=.R-8.4 Explain how to implement a priority queue based on the composition method (of storing key-element pairs) by adapting a priority queue based on the comparator approach.

R-8.5 Suppose you label each node v of a binary tree T with a key equal to the preorder rank of v. Under what circumstances is T a heap?

R-8.6 Show the output from the following sequence of priority queue ADT operations. The entries are key-element pairs, where sorting is based on the key value:

insert(5, a),insert(4, b),insert(7, i),insert(1, d),removeMin(), insert(3, j),insert(6, c),removeMin(), removeMin(), insert(8, g),remove-Min(), insert(2, h),removeMin(), removeMin().R-8.7 An airport is developing a computer simulation of air-traffic control that handles events such as landings and takeoffs. Each event has a time-stamp that denotes the time when the event occurs. The simulation program needs to efficiently perform the following two fundamental operations:

Insert an event with a given time-stamp (that is, add a future event)

Extract the event with smallest time-stamp (that is, determine the next event to process)

Which data structure should be used for the above operations? Why?

R-8.8 Although it is correct to use a "reverse" comparator with our priority queue ADT so that we retrieve and remove an element with the maximum key each time, it is confusing to have an element with the maximum key returned by a function named "

removeMin." Write a short adapter class that can take any priority queue P and an associated comparator C and implement a priority queue that concentrates on the element with the maximum key, using functions with names likeremoveMax.(Hint: Define a new comparator C′ in terms of C.)

R-8.9 Illustrate the performance of the selection-sort algorithm on the following input sequence: (22,15,36,44,10,3,9,13,29,25).

R-8.10 Illustrate the performance of the insertion-sort algorithm on the input sequence of the previous problem.

R-8.11 Give an example of a worst-case sequence with n elements for insertion-sort, and show that insertion-sort runs in Ω(n

^{2}) time on such a sequence.R-8.12 At which nodes of a heap can an entry with the largest key be stored?

R-8.13 In defining the relation "to the left of" for two nodes of a binary tree (Section 8.3.1), can we use a preorder traversal instead of an inorder traversal? How about a postorder traversal?

R-8.14 Illustrate the performance of the heap-sort algorithm on the following input sequence: (2,5,16,4,10,23,39,18,26,15).

R-8.15 Let T be a complete binary tree such that node v stores the key-entry pairs (f(v),0), where f(v) is the level number of v. Is tree T a heap? Why or why not?

R-8.16 Explain why the case where the right child of r is internal and the left child is external was not considered in the description of down-heap bubbling.

R-8.17 Is there a heap T storing seven distinct elements such that a preorder traversal of T yields the elements of T in sorted order? How about an inorder traversal? How about a postorder traversal?

R-8.18 Consider the numbering of the nodes of a binary tree defined in Section 7.3.5, and show that the insertion position in a heap with n keys is the node with number n + 1.

R-8.19 Let H be a heap storing 15 entries using the vector representation of a complete binary tree. What is the sequence of indices of the vector that are visited in a preorder traversal of H? What about an inorder traversal of H? What about a postorder traversal of H?

R-8.20 Show that the sum , which appears in the analysis of heap-sort, is Ω(nlogn).

R-8.21 Bill claims that a preorder traversal of a heap will list its keys in nondecreasing order. Draw an example of a heap that proves him wrong.

R-8.22 Hillary claims that a postorder traversal of a heap will list its keys in non-increasing order. Draw an example of a heap that proves her wrong.

R-8.23 Show all the steps of the algorithm for removing key 16 from the heap of Figure 8.3.

R-8.24 Draw an example of a heap whose keys are all the odd numbers from 1 to 59 (with no repeats), such that the insertion of an entry with key 32 would cause up-heap bubbling to proceed all the way up to a child of the root (replacing that child's key with 32).

R-8.25 Give a pseudo-code description of a nonrecursive in-place heap-sort algorithm.

R-8.26 A group of children want to play a game, called Unmonopoly, where in each turn the player with the most money must give half of his/her money to the player with the least amount of money. What data structure(s) should be used to play this game efficiently? Why?