PriorityQueueTest Explicit check of lists as priority queues

Queue to maximize the "through-put" statistics:  always take the queued job that has the shortest requested time, so we'll call it the "Lazy" Queue.  That is accomplished by using a priority queue implemented as a MinHeap.

JobEntry.java        Class of Comparable objects entered into the heaps — compareTo() based on an int field.  Txt file.
MinHeap.java       Min-heap implementation:  queue where smallest entries are taken first.  Txt file.
TestHeap.java       Initial test program.  Txt file.
LazyQueue.rtf         Code as a two-sheet two-column-text word-processor file
LazyQueue.jar        Executable jar with the above Java classes

16-run Slide.doc    Slide set showing generation of a 16-item min-heap, then its emptying
16-run Trace.doc   Textual trace of the enqueue/dequeue operations shown
16_Demo Trace     The slide set as a series of web pages

Heapify.rtf             Amplify MinHeap to allow straight data entries, followed by heap correction
Heapify Files         Source code — for the extension both of MinHeap and of MinHeap0 (see below)

Heap[1] Drill:       root at [1]:  Heap generation by enqueue, by Enter/FixHeap; Heap dequeues.

MinHeap0.java      Min-heap is altered to begin with subscript [0], not [1].  Txt file.
TestHeap0.java     Corresponding main.
QueueDiffs.rtf        Heap algorithmic differences between MinHeap.java and MinHeap0.java
Q_Diff.html            Above in HTML form
LazyQueue0.jar      Executable jar

Heap[0] Drill:        root at [0]:  Heap generation by enqueue, by Enter/FixHeap; Heap dequeues.

HeapArray.java     MinHeap0 implementation of DownHeap (altered to a max-heap) generates a sorting algorithm.  Txt file.
HeapArray.jar        Executable jar — program comparable with the earlier sorting benchmarks.  Click here.
HeapStats.xls         Excel workbook showing results from two experimental runs with that program.
HeapStat100.gif     Plot of results from  to 100.
HeapStat5k.gif       Plot of results from 100 to 5000.

CkSorts                  Bench marking:  Heap- versus Merge- versus Quick- versus optimized Quick-Sort

HeapDemo.html     Detailed trace of sorting "A SORTING EXAMPLE" (with thanks to Robert Sedgewick)

Sorting Animation   Includes Heap Sort as an animation option

Enrichment Material

One can prove that the transformation of an unsorted array into a heap through the loop at the end of Carrano's Ch. 11 (the segment on heapSort) requires O(N) time rather than O(N log N) time.  Note:  this write-up uses the majority convention in which the root is at depth zero and leaves are at height zero.

WorstFix.doc        Two proofs, one building from an earlier recurrence, the other from an earlier text.