- In the Accident and Emergency department of a hospital, this
assessment is called
*triage*. - A printer or other shared computer resource ought to process small jobs quickly, and leave big ones until a quiet period.
- The basic idea of
**selection sort**- to find the next smallest value - can be implemented in*O*(*n*log*n*) time instead of*O*(*n*^{2}) since heaps provide the next smallest value in*O*(log*n*) time instead of*O*(*n*). - We shall use priority queues later as a subroutine in searching for the shortest path between points in a network.

- the shortest version of the code is utterly meaningless,
so you
*have*to use theory to get it to work, and - it contains several traps that nicely test students' understanding of the algorithm.

class HeapX implements HeapXing { final static int ROOT = 0; public int root () { return ROOT; } public int parent (int child) { return ???; } public int left_child (int parent) { return ???; } public int right_child (int parent) { return ???; } public int sibling (int child) { return ???; } public void choice (int c) {} public void heap_X (...) { } }A

- you pass from
`position`to`parent(position)`, not to`position+1`, and - you only make one pass up the tree, since the rest of it is assumed already to be in heap order, so
- really it's more like
*insertion sort*, as the ancestors (parent, grandparent, ...) are successively demoted, and then the new value is inserted once.

trace sift-upin the usual way. The array will be shown as a tree, with the branches drawn in different ways depending on whether heap order is satisfied or not. Sifting up very often terminates after one generation, so you may have to run it several times to see it working. The

class SiftUp implements HeapSiftingUp { public void sift_up (int[] array, int position, int contents) { } }The

Trace.printheap (int root, boolean root_is_max, int[] array, int contents);for which the first two arguments should be

- there may be 0, 1, or 2 children - don't forget the case of 1 child - and
- the values of the parent, left and right children need to be compared.

class SiftDown implements HeapSiftingDown { void sift_down (int[] array, int position, int contents) { } }Once again, the

trace heapify-by-insertionto watch the model answer in the TESTER doing this. The template is as follows, together with the

class Heapify implements Heapifying { public int[] heapify (int[] array, int contents) { } private HeapSiftingUp sifter_up; public Heapify () { sifter_up = new TestHeapUp(); // or SiftUp() to use your own code } }The

trace heapify-by-sifting-downto watch the model answer in the TESTER doing this. In

class Heap { private int capacity; private int contents; private int [ ] array; final static int ROOT = 0; public int root () { return ROOT; } private int parent (int child) { return ???; } private int left_child (int parent) { return ???; } private int right_child (int parent) { return ???; } private int sibling (int child) { return ???; } private int choice = 0; public void choice (int c) { choice=c; } // make a new heap with contents=0 and capacity=size public Heap (int size) { ??? } // make a new heap with default size public Heap () { this (10); } // make a new heap by heafifying a given array public Heap (int[ ] data) { ??? } // transfer the heap to a bigger array (cf. jugs) private void rebuild (int new_size) { ??? } private sift_up (int position) { ??? } private sift_down (int position) { ??? } public void insert (int new_value) { ??? } public int delete_root () { ??? } private void heapify () { ??? } public int[ ] sort_me () { ??? } // use a "new Heap" so that your class "implements Sorting" public int[ ] sort (int[ ] array) { ??? } // maybe write your own (command line) user interface public static void main (String[ ] args) { ??? } }You can add other methods to make this class implement the various TESTER interfaces and thereby re-test your code. However, the TESTER will only allow you to do these one at a time.

This is
`www.PaulTaylor.EU/algorithms/heap.html`
and it was derived from `algorithms/heap.tex`
which was last modified on 21 July 2007.