heapSort.java

// insert
void minHeapUp(int[] arr, int i) {
	int j = (i - 1) / 2; // parent index
	int tmp = arr[i];
	while (j >= 0 && i != 0) {
		if (arr[j] <= arr[i]) {
			break;
		}
		arr[i] = arr[j];
		i = j;
		j = (i - 1) / 2;
	}
	arr[i] = tmp;
}

a[n] = numToInsert;
minHeapUp(arr, n);

// delete
void minHeapDown(int[] arr, int i, int n) {
	int j = 2 * i + 1; // left child index
	int tmp = arr[i];
	while (j < n) {
		if (j + 1 < n && arr[j+1] < arr[j]) {
			j ++; // go to right child
		}
		if (a[j] >= tmp) {
			break;
		}
		arr[i] = arr[j];
		i = j;
		j = 2 * i + 1;
	}
	arr[i] = tmp;
}

swap(arr[0], arr[n-1]);
minHeapDown(arr, 0, n - 1);

// construct min heap
for (int i = (n - 1 - 1) / 2; i >= 0; i --) {
	minHeapDown(arr, i, n);
}

// heap sort
for (int i = n - 1; i >= 1; i--)  
{  
    swap(arr[i], arr[0]);  
    minHeapDown(arr, 0, i);  
}