CSC212 Lab 12 2014

--D. Thiebaut (talk) 19:37, 9 November 2014 (EST)

---

Lab Problem #1

• Java provides heap data structures, but calls them PriorityQueues.
• Instead of keeping the largest element at the top of the heap, PriorityQueues keep the smallest elements at the top.
• Try the example below to see how to use a PriorityQueue

import java.util.PriorityQueue;

public class HeapPriorityQueue {
	
	public static void main(String[] args) {
		PriorityQueue<Integer> heap = new PriorityQueue<Integer>();

		heap.add( 1 );
		heap.add( 20 );
		heap.add( 5 );
		heap.add( 100 );
		while ( ! heap.isEmpty() )
			System.out.println( heap.poll() );
	}
}

Question 1

Using some of the code/functions from this page, create a function called heapsort( int[] A ) that will use a priority queue to sort the array of ints A.

Question 2

Using the code snippet below, measure the execution times of QuickSort and of your HeapSort function. Figure out which is regularly faster on arrays of varying sizes.

        long start = System.nanoTime();
        quicksort(A, 0, A.length - 1);
        long end   = System.nanoTime();
        System.out.println( String.format(   
                                "quickSort( %d ) takes %1.3f msec", N,
                               (end-start)/1000000.0f ) );