Heap sorts
sort the elements based on heap data structure.
Heap is a
tree kind of data structure that satisfies heap property. There are two kinds
of heaps.
Max Heap
In a max
heap, the keys of parent nodes are always greater than or equal to those of the
children and the highest key is in the root node.
How to construct max heap
Following
link explains it clearly.
Example
Min Heap
In a min
heap, the keys of parent nodes are always greater than or equal to those of the
children and the lowest key is in the root node.
How to construct a Min heap
Following
link explains it clearly.
Sorting elements in ascending order
Step 1: Build max heap.
Step 2: Swap element at 0th position with last element
of the array.
Step 3: Decrement the length of the array.
Step 4: Call maxHeap method on element 0. Repeat steps2 to
3 until length of array > 0.
import java.util.Objects; public class HeapSort<T extends Comparable<T>> { private T arr[]; private int length; /** * If flag is true, then elements are sorted in ascending order, else * descending order */ public void sort(T[] arr, boolean flag) { Objects.nonNull(arr); this.arr = arr; length = arr.length; if (flag == true) sortAscending(arr); else sortDescending(arr); } private void sortDescending(T arr[]) { buildMinHeap(); swap(0, length - 1); length--; while (length > 0) { minHeap(0); swap(0, length - 1); length--; } } private void sortAscending(T arr[]) { buildMaxHeap(); swap(0, length - 1); length--; while (length > 0) { maxHeap(0); swap(0, length - 1); length--; } } private void buildMaxHeap() { int start = length / 2; for (int i = start - 1; i > -1; i--) { maxHeap(i); } } private void buildMinHeap() { int start = length / 2; for (int i = start - 1; i > -1; i--) { minHeap(i); } } private void minHeap(int position) { int left = 2 * position + 1; int right = left + 1; int temp = position; if (left < length && arr[left].compareTo(arr[temp]) < 0) temp = left; if (right < length && arr[right].compareTo(arr[temp]) < 0) temp = right; if (temp == position) return; swap(position, temp); minHeap(temp); } private void maxHeap(int position) { int left = 2 * position + 1; int right = left + 1; int temp = position; if (left < length && arr[left].compareTo(arr[temp]) > 0) temp = left; if (right < length && arr[right].compareTo(arr[temp]) > 0) temp = right; if (temp == position) return; swap(position, temp); maxHeap(temp); } private void swap(int i, int j) { T temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } }
Following is
the junit test case for above program.
import static org.junit.Assert.assertTrue; import java.util.Arrays; import org.junit.Test; public class HeapSortTest { @Test public void test1() { HeapSort<Integer> heapSort = new HeapSort<>(); Integer arr1[] = { 2, 4, 6, 8, 1, 3, 5, 7 }; Integer arr2[] = { 5, 46, 25, 13, 12 }; Integer arr3[] = { 5, 46 }; heapSort.sort(arr1, true); assertTrue(Arrays .equals(arr1, new Integer[] { 1, 2, 3, 4, 5, 6, 7, 8 })); heapSort.sort(arr1, false); assertTrue(Arrays .equals(arr1, new Integer[] { 8, 7, 6, 5, 4, 3, 2, 1 })); heapSort.sort(arr2, true); assertTrue(Arrays.equals(arr2, new Integer[] { 5, 12, 13, 25, 46 })); heapSort.sort(arr2, false); assertTrue(Arrays.equals(arr2, new Integer[] { 46, 25, 13, 12, 5 })); heapSort.sort(arr3, true); assertTrue(Arrays.equals(arr3, new Integer[] { 5, 46 })); heapSort.sort(arr3, false); assertTrue(Arrays.equals(arr3, new Integer[] { 46, 5 })); } }
No comments:
Post a Comment