Review 8: Priority queues

Problem 8.1.1.

Name and briefly describe each of the major operations in the PQueue ADT.

Problem 8.1.2.

Suppose we are using an ordered array to store a priority queue, stored in descending order. Using Big-O notation in terms of the current priority queue's size n, what is the tightest possible bound for each of the following operations? Explain your answers.

• a. add
• b. remove

Problem 8.1.3.

Suppose we have an implementation of the PQueue interface called PQImpl, with a no-arguments constructor method creating an empty priority queue. Complete the following class method so that it uses a PQImpl object to put the elements of the array in sorted order.

public static void sort(String[] data) {

    PQueue<String> q = new PQImpl<String>();
    for(int i = 0; i < data.length; i++) q.add(data[i]);
    for(int i = 0; i < data.length; i++) data[i] = q.remove();
}

Problem 8.1.4.

Suppose you are to implement the PQueue interface using an array, where the array is stored in arbitrary order. That is, we do not maintain the invariant that the array is in descending order, and in fact methods can reorder the elements if convenient. The following is a start to the implementation; complete the remove method. (And don't bother writing the peek method.)

public class ArrayPQueue<E> implements PQueue<E> {
    private E[] elements;
    private int numElements;

    public ArrayPQueue(int capacity) {
        elements = (E[]) new Object[capacity];
        numElements = 0;
    }

    public boolean isEmpty() {
        return numElements == 0;
    }

    public void add(E value) {
        elements[numElements] = value;
        numElements++;
    }

    public E remove() {
        // remember to raise NoSuchElementException if queue is empty.

		if(numElements == 0) throw new NoSuchElementException();

		E min = elements[0];
		int minPos = 0;
		for(int i = 1; i < numElements; i++) {
			E t = elements[i];
			if(t.compareTo(ret) < 0) { min = t; minPos = i; }
		}

		numElements--;
		elements[minPos] = elements[numElements];
		return min;
	}

Problem 8.2.1.

Identify the data structure invariants that describe the structure of a heap. (We identified two in class; you should describe both for full credit.)

Problem 8.2.2.

Suppose we insert 3 into the heap whose tree diagram is below. What will its tree diagram then be?

Problem 8.2.3.

Suppose we insert 20 into the heap whose tree diagram is below. What will its tree diagram then be?

Problem 8.2.4.

Suppose we remove the minimum from the heap whose tree diagram is below. What will its tree diagram then be?

Problem 8.2.5.

Suppose we remove the minimum twice from the heap whose tree diagram is below. What will its tree diagram then be?

after one removal:
after two removals:

Problem 8.2.6.

How much time does the add operation take for a heap? Use big-O notation in terms of the number of values n in the heap. Explain your answer.

Problem 8.2.7.

Draw the array representation of a heap whose tree diagram is as follows.

Problem 8.2.8.

Suppose we have an array whose contents represent a heap, and suppose i is an index an array element/heap node n. Give a Java arithmetic expression representing each of the following.

Problem 8.2.9.

Suppose we have a heap of integers stored in an array as follows. What would the array contain after a single remove operation?

Problem 8.2.10.

Suppose we have the following array representing a heap as seen in class (where lower numbers represent higher-priority elements). What will the array contain following an insertion of the number 4 into the heap?

Problem 8.3.1.

How does heapsort compare to quicksort in terms of big-O efficiency? And how do they compare in practice?

Problem 8.4.1.

Write Dijkstra's algorithm using pseudocode. That is, you should write it in something resembling code, but you can use English words to describe the individual steps.

Problem 8.4.2.

Suppose we implement Dijkstra's algorithm so that we add a neighbor into the priority queue only when the neighbor has not already been visited. Run this algorithm to find the shortest path from the gray node to the black node on the graph below, and number each edge (road) as it is processed (beginning with 1.).

[There is a tie in choosing between the fourth and fifth edge. The answer reversing the order of these two edges is also correct.]

Problem 8.4.3.

Suppose we run Dijkstra's algorithm to find the shortest path from the gray node to the black node in the map at right. Number each node (beginning with 1. for the first node removed from the priority queue).

Problem 8.4.4.

Use A* search to determine the shortest route from Clinton to Mountain Home using the map at right. For your heuristic, use the straight-line distance (as the crow flies) from each town to Mountain Home, as follows.

52	Clinton
86	Conway
63	Heber Springs
0	Mountain Home
36	Mountain View
34	Pindall
19	Yellville

Write down the towns in the order they are added to the priority queue. (You need not add towns into the queue if they have already been visited.) When the algorithm visits a town, cross it out and place a number next to it indicating the order in which towns are visited.

Problem 8.4.5.

Suppose we find ourselves stuck in the middle of Houston and we want to get to Amarillo. (These problems don't have to be realistic, do they?) We have in our hands the following simplified road map of Texas, and we decide to use the A* algorithm. List the cities in the order they are placed into visited. (Note that not all cities will necessarily be visited in the course of the algorithm.)