#ifndef HEAP_SORT_HH #define HEAP_SORT_HH template void Heapify(ItemType* A, unsigned i, unsigned heapsize) { while(true) { unsigned l = 2*i+1; unsigned r = 2*i+2; unsigned largest = (l < heapsize && A[i] < A[l]) ? l : i; if(r < heapsize && A[largest] < A[r]) largest = r; if(largest != i) { ItemType tmp = A[i]; A[i] = A[largest]; A[largest] = tmp; i = largest; } else break; } } template void HeapSort(ItemType* array, unsigned size) { for(unsigned i = size/2; i > 0;) Heapify(array, --i, size); for(unsigned i = size-1; i>0; --i) { ItemType tmp = array[0]; array[0] = array[i]; array[i] = tmp; Heapify(array, 0, i); } } #endif