Heap Sort - Coursera Algorithms

Heap Sort is an in place sort that builds a max binary heap and then repeatedly deletes the maximum element. It's not stable and it's inner loop takes longer than Quick Sort. It has poor cache usage. To build a heap, it takes O(N) and for sort, it takes O(NlogN).

Following is the program:

	package sorting.heapSort;
	public class HeapSort<Key extends Comparable<Key>> {
	public void sort(Comparable[] a) {
	int indx = a.length-1;
	for(int k=indx/2;k>=1;k--) {
	sink(a,k,indx);
	}
	print(a); //max heap
	while(indx>1) {
	exchange(a,1,indx);
	sink(a,1,--indx);
	}
	}
	public boolean less(Comparable[] a,int aa, int bb) {
	return a[aa].compareTo(a[bb])<0;
	}
	public void exchange(Comparable[] a,int i, int j) {
	Comparable tmp = a[i];
	a[i] = a[j];
	a[j] = tmp;
	}
	public void print(Comparable[] a) {
	System.out.println();
	int indx = a.length-1;
	for(int i=1;i<=indx;i++) {
	System.out.print(a[i]+"--");
	}
	}
	private void sink(Comparable[] a,int k, int indx) {
	while(2*k <= indx) {
	int j = 2*k;
	if(j<indx && less(a,j,j+1)) j++;
	if(!less(a,k,j)) break;
	exchange(a,k, j);
	k=j;
	}
	}
	public static void main(String[] args) {
	HeapSort<String> pq = new HeapSort<String>();
	Integer[] a = {-1,5,2,4,6,1,3};
	// String[] a = {"*","S","O","R","T","E","X","A","M","P","L","E"};
	pq.print(a);
	pq.sort(a);
	pq.print(a);
	}
	}

view raw HeapSort.java hosted with ❤ by GitHub

Related Posts:

Binary Heap