Added heap sort

rrivera1849 · rrivera1849 · commit 9a080669c865 · 2014-01-03T04:20:42.000-04:00
diff --git a/Heap_Sort/Java/rrivera1849/Heap.java b/Heap_Sort/Java/rrivera1849/Heap.java
@@ -1,6 +1,6 @@
 /*
  * Written by: Rafael A. Rivera Soto
- * Last Updated: January 2, 2013
+ * 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.
diff --git a/Heap_Sort/Java/rrivera1849/Heap.java~ b/Heap_Sort/Java/rrivera1849/Heap.java~
@@ -0,0 +1,62 @@
+/*
+ * Written by: Rafael A. Rivera Soto
+ * Last Updated: January 2, 2013
+ * 
+ * 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;
+	}
+}
diff --git a/Heap_Sort/Java/rrivera1849/Heap_Sort.java b/Heap_Sort/Java/rrivera1849/Heap_Sort.java
@@ -1,6 +1,6 @@
 /*
  * Written by: Rafael A. Rivera Soto
- * Last Updated: January 2, 2013
+ * Last Updated: January 2, 2014
  */
 public class Heap_Sort {
 	/*
diff --git a/Heap_Sort/Java/rrivera1849/Heap_Sort.java~ b/Heap_Sort/Java/rrivera1849/Heap_Sort.java~
@@ -0,0 +1,32 @@
+/*
+ * Written by: Rafael A. Rivera Soto
+ * Last Updated: January 2, 2013
+ */
+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();
+	}
+}

Original file line number	Diff line number	Diff line change
`@@ -1,6 +1,6 @@`
`1`	`1`	`/*`
`2`	`2`	`* Written by: Rafael A. Rivera Soto`
`3`		`- * Last Updated: January 2, 2013`
	`3`	`+ * Last Updated: January 2, 2014`
`4`	`4`	`*`
`5`	`5`	`* This class only contains the necessary methods needed to build a maxHeap and sort`
`6`	`6`	`* our array. It is in no way representative of a real heap implementation.`