Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public final class HeapSort {
- public static <T extends Comparable<? super T>> void sort(T[] array) {
- int lastLeaf = array.length - 1;
- heapify(0, array);
- for(int i = 0; i < array.length; i++) {
- array[lastLeaf] = removeMax(lastLeaf, array);
- lastLeaf--;
- }
- }
- private static <T extends Comparable<? super T>> void fixHeap(int index, T[] heap, int lastLeaf) {
- if(2*index+1 > lastLeaf && 2*index+2 >lastLeaf) return;
- else {
- int maxChildIndex = maxChildIndex(index, heap, lastLeaf);
- if(heap[index].compareTo(heap[maxChildIndex]) < 0) {
- T tmp = heap[index];
- heap[index] = heap[maxChildIndex];
- heap[maxChildIndex] = tmp;
- fixHeap(maxChildIndex, heap, lastLeaf);
- }
- }
- }
- private static <T extends Comparable<? super T>> int maxChildIndex(int index, T[] heap, int lastLeaf) {
- if(2*index+1 > lastLeaf) return 2*index+2;
- if(2*index+2 > lastLeaf) return 2*index+1;
- return(heap[2*index+1].compareTo(heap[2*index+2]) < 0) ? 2*index+2 : 2*index+1;
- }
- private static <T extends Comparable<? super T>> void heapify(int index, T[]heap) {
- if(index >= heap.length) return;
- heapify(2*index+1, heap);
- heapify(2*index+2, heap);
- fixHeap(index, heap, heap.length-1);
- }
- private static <T extends Comparable<? super T>> T removeMax(int lastLeaf, T[]heap) {
- T max = heap[0];
- heap[0] = heap[lastLeaf];
- fixHeap(0, heap, lastLeaf-1);
- return max;
- }
- public static void main(String[] args) {
- Integer[] a = {84,2,7,3,25,14,35,65,88,4};
- System.out.println(java.util.Arrays.toString(a));
- sort(a);
- System.out.println(java.util.Arrays.toString(a));
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement