CS 261, Spring 2013, Homework 4 Due Thursday, May 9 1. Suppose that a binary heap contains the four values 1, 2, 3, and 4 (with smaller numbers meaning higher priority). List all of the permutations of these values that represent valid configurations of the heap. 2. Suppose that we have a binary heap with n numbers in it, again with smaller numbers meaning higher priority. We know that the minimum of the numbers is in position 0 of the heap. How many different positions could possibly hold the maximum of the numbers? (You should assume that all the numbers are different from each other.) 3. Consider the following naive representation of a priority queue: we represent the queue as a dynamic array of the data values, with no constraints on how they are ordered. To find the minimum value, we search through the whole array. (a) What are the amortized time bounds for the add, decrease priority, and delete min operations in this structure? Give your answers in O-notation as a function of n, the number of values in the priority queue. (b) If we are using a priority queue to implement Dijkstra's shortest path algorithms, are there graphs for which this naive method would lead to a total time bound that is the same as or better than the bound given by using Fibonacci heaps? If yes, describe these graphs. If no, explain why not. 4. Suppose that we perform the following two operations on a Fibonacci heap: first, create a new heap from a given set of n values, and second, perform a single delete-min operation. How many trees will there be in the structure that we finish with, as a function of n? (Hint: consider the binary representation of n.)