import java.awt.*;

public class HeapSort extends ShowSort {
	int piv=0;
	
	public static void main(String args[]) {
		HeapSort applet = new HeapSort();
		applet.launch("HeapSort");
	}

	void doSort() {
		inplace_dir = true;
		inplace_pos = NUM;
		heapSort(array, 0, NUM-1);
	}

	void heapSort(int array[], int bottom, int top) {
		int t;

		curr_bar_color = Color.green;
		heapify(array, bottom, top);
		curr_bar_color = Color.red;
		
		for (t=top; t>bottom; t--) {
			inplace_pos = t;
			
			int temp=array[bottom];
			array[bottom] = array[t];
			array[t] = temp;
			swapped(t);
			
			walk_down(array, bottom, t-1);
		}
		inplace_pos = 0;
	}

	void heapify(int array[], int bottom, int top) {
		int root;
		for (root=top/2; root>=bottom; root--) {
			walk_down(array, root, top);
		}
	}
	

	void walk_down(int array[], int bottom, int top) {
		int largest;
		int pos = bottom;

		while ((2*pos+1) <= top) {
			if ((2*pos+2) <= top) {
				largest = (array[2*pos+1] > array[2*pos+2]) ? (2*pos+1) : (2*pos+2);
				compared(2*pos+2);
			} else {
				largest = 2*pos+1;
			}

			compared(pos);
			
			if(array[pos] <= array[largest]) {
				int temp = array[largest];
				array[largest] = array[pos];
				array[pos] = temp;
				swapped(largest);
			}
			pos = largest;
		}
	}
}