GROUP WORK

1. a. Show the result of heapsort on E, C, H, A, G, D, F, B


	















b. What is the Big-O bound for buildHeap (heapify)?
c. What is the Big-O bound for Heap Sort?

As reference, here is the code for Heap Sort:

	void heapsort(Comparable[] array) {
	    for (int i = array.length/2; i >= 0; i--)   // heapify
	        percolateDown(array, i, array.length);	// heapify
	    for (int j = array.length-1; i > 0; i--) {  
	        swap(array, 0, j);
			percolateDown(array, 0, j);
	    }
	}


2. Draw a picture of (a) Array Stack, (b) Array Queue, (c) Linked-List Stack, and (d) Linked-List Queue.  Include all necessary pointers.  Discuss what happens as you add and remove items from each.  (In particular, what happens when you exceed the initial array capacity.)