class HeapSort extends SortAlgorithm {
	void downheap(int a[], int N, int k) {
		int j; int v = a[k];
		while (k <= N/2) {
			j = k+k;
			if (j < N && a[j] < a[j+1]) j++; 
			if (v >= a[j]) break;
			a[k] = a[j]; k = j;
			pause();
		}
		a[k] = v;
	}
	
    void sort(int a[]) {
	    int N = a.length-1;
		for (int k = (N-1)/2; k >= 0; k--) 
			downheap(a, N, k);
		while (N > 0)
			{ swap(a, 0, N); downheap(a, --N, 0); }
	}
}