heap sort


See On Github

Data

Source Code

/*
 * Written by: Rafael A. Rivera Soto
 * Last Updated: January 2, 2014
 * 
 * This class only contains the necessary methods needed to build a maxHeap and sort
 * our array. It is in no way representative of a real heap implementation.
 */
public class Heap {
	int [] array;
	int size;
	
	public Heap(int[] array) {
		this.array = array;
		this.size = array.length;
		buildMaxHeap();
	}
	
	public int leftIndex(int i){
		return 2*i + 1;
	}
	
	public int rightIndex(int i){
		return 2*i + 2;
	}
	
	public void swap(int index1, int index2){
		int temp = array[index1];
		array[index1] = array[index2];
		array[index2] = temp;
	}
	
	public void maxHeapify(int i){
		int l = leftIndex(i);
		int r = rightIndex(i);
		int largest;
		
		if(l < size && array[l] > array[i]){
			largest = l;
		}else{
			largest = i;
		}
		
		if(r < size && array[r] > array[largest]){
			largest = r;
		}
		
		if(largest != i){
			swap(i,largest);
			maxHeapify(largest);
		}
	}
	
	public void buildMaxHeap(){
		for(int i = size/2 - 1; i >= 0; i--){
			maxHeapify(i);
		}
	}
	
	public int[] getArray(){
		return array;
	}
}
/*
 * Written by: Rafael A. Rivera Soto
 * Last Updated: January 2, 2014
 */
public class Heap_Sort {
	/*
	 * Description:
	 * 		Represents the array as a heap in order to effectively sort it. Uses functions
	 * implemented in the heap class in order to build the heap as a "max heap" and then 
	 * sort.
	 * 
	 * Input:
	 * 		array:int - sequence to sort
	 * 
	 * Output:
	 * 		A sorted array.
	 * 
	 * Complexity:
	 * 		O(nln(n))
	 */
	public static int[] heapSort(int[] array){
		Heap arrayHeap = new Heap (array);
		
		for(int i = arrayHeap.size - 1; i > 0; i--){
			arrayHeap.swap(i, 0);
			arrayHeap.size -= 1;
			arrayHeap.maxHeapify(0);
		}
		
		return arrayHeap.getArray();
	}
}
import static org.junit.Assert.*;

import org.junit.Assert;
import org.junit.Test;

import java.util.Arrays;

public class Heap_Sort_test extends Heap_Sort{

	@Test
	public void test() {
		int[] unsorted = {38,32,13,45,-32,-123,0};
		int[] sorted = {-123,-32,0,13,32,38,45};
		int[] result = heapSort(unsorted);
		
		String errorMsg = String.format("Error - expected %s got %s",Arrays.toString(sorted),
				Arrays.toString(result));
		
		Assert.assertArrayEquals(errorMsg, sorted, result);
	}

}