040: // Based on the code at:
041: //  http://clips.ee.uwa.edu.au/~morris/year2/PLDS210/Java/heap_sort/ComBox.class
042: //  by John Morris, Centre for Intelligent Information Processing Systems
043: //  Course notes for Programming Languages and Data Structures PLDS210
044: //  The code presented here is based on the code attached to the animation
045: //  of the Heap Sort, animation by Woi Ang.
046: //
047: //  The original code does not compile because setHeapWithSize is not defined
048: //
049: //  Simple substitution of an array for a heap will not work because of the
050: //  intertwined use of .length.  When an array is used for a heap, if frequent
051: //  checks are to avoided, the size of the array must be one less than a
052: //  power of 2 to allow all parents to have children.  The original algorithm,
053: //  however, uses .length to get the occupied portion of the heap.
054: //
055: //  In this simple fix, we define a class, Heap, that combines an array with
056: //  a length, and take the lazy way out, making the array bigger than in needs
057: //  to be (twice the occupied size).  For a space-efficient production version,
058: //  the next power of 2 above the occupied size should be computed.
059: //
060: //  Revisions by H. J. Bernstein, 10 March 2004.
061: 
062: 
063: public class HeapSort {
064: 
065: public class Heap {
066:    public int length;
067:    public int [] array;
068:    public Heap (int size) {
069:      array = new int[size*2];
070:      length = size;
071:    }
072: }
073: 
074: public void heapsort(int [] a ) {
075:   Heap A = setHeapWithSize(a, a.length);
076:   buildHeap(A);
077:   printHeap(A);
078:   for (int i = a.length; i > 1; i--) {
079:     a[i-1] = A.array[0]; A.array[0] = A.array[i-1];
080:     A = setHeapWithSize(A.array,A.length -1);
081:     heapify(A, 1);
082:     printHeap(A);
083:   }
084:   a[0] = A.array[0];
085: }
086: 
087: public void printHeap(Heap a ) {
088:   for (int i = 0; 2*i+2 < a.length; i++) {
089:     System.out.println("Node "+(i+1)+": "+a.array[i]+" Left: "+a.array[2*i+1]+
090:       " Right: "+a.array[2*i+2]);
091:   }
092: }
093: 
094: public Heap  setHeapWithSize(int [] a, int len) {
095:   Heap result;
096:   result = new Heap(len);
097:   for (int i = 0; i < len; i++) {
098:     result.array[i] = a[i];
099:   }
100:   return result;
101: }
102: 
103: public void buildHeap(Heap a) {
104:   for (int i = a.length/2; i > 0; i--) {
105:     heapify(a,i);
106:   }
107: }
108: 
109: public void heapify(Heap a, int i) {
110:   int l = left(i);
111:   int r = right(i);
112:   int largest;
113:   if ( i < heapSize(a) && a.array[l-1] > a.array[i-1]) {
114:     largest = l;
115:   } else {
116:     largest = i;
117:   }
118:   if ( r <= heapSize(a) && a.array[r-1] > a.array[largest -1]){
119:     largest = r;
120:   }
121:   if (largest != i) {
122:     // exchange a[i], a[largest]
123:     int tmp = a.array[i-1]; a.array[i-1] = a.array[largest-1]; 
124:       a.array[largest-1] = tmp;
125:     heapify(a, largest);
126:   }
127: }
128: 
129: 
130: public int heapSize(Heap a){
131:   return a.length;
132: }
133: 
134: public int parent(int i) {
135:   return (i/2);
136: }
137: 
138: public int left(int i) {
139:    return (2*i);
140: }
141: 
142: public int right(int i) {
143:   return (2*i + 1);
144: }
145: 
146: }