Advertisement
Guest User

HELP - I NEED TO REPLACE THE ARRAY WITH THE LIST!

a guest
Jan 23rd, 2017
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 1.69 KB | None | 0 0
  1. public final class HeapSort {
  2.  
  3.     public static <T extends Comparable<? super T>> void sort(T[] array) {
  4.         int lastLeaf = array.length - 1;
  5.         heapify(0, array);
  6.         for(int i = 0; i < array.length; i++) {
  7.             array[lastLeaf] = removeMax(lastLeaf, array);
  8.             lastLeaf--;
  9.         }
  10.     }
  11.  
  12.     private static <T extends Comparable<? super T>> void fixHeap(int index, T[] heap, int lastLeaf) {
  13.         if(2*index+1 > lastLeaf && 2*index+2 >lastLeaf) return;
  14.         else {
  15.             int maxChildIndex = maxChildIndex(index, heap, lastLeaf);
  16.             if(heap[index].compareTo(heap[maxChildIndex]) < 0) {
  17.                 T tmp = heap[index];
  18.                 heap[index] = heap[maxChildIndex];
  19.                 heap[maxChildIndex] = tmp;
  20.                 fixHeap(maxChildIndex, heap, lastLeaf);
  21.             }
  22.         }
  23.     }
  24.  
  25.     private static <T extends Comparable<? super T>> int maxChildIndex(int index, T[] heap, int lastLeaf) {
  26.         if(2*index+1 > lastLeaf) return 2*index+2;
  27.         if(2*index+2 > lastLeaf) return 2*index+1;
  28.         return(heap[2*index+1].compareTo(heap[2*index+2]) < 0) ? 2*index+2 : 2*index+1;
  29.     }
  30.  
  31.     private static <T extends Comparable<? super T>> void heapify(int index, T[]heap) {
  32.         if(index >= heap.length) return;
  33.         heapify(2*index+1, heap);
  34.         heapify(2*index+2, heap);
  35.         fixHeap(index, heap, heap.length-1);
  36.     }
  37.  
  38.     private static <T extends Comparable<? super T>> T removeMax(int lastLeaf, T[]heap) {
  39.         T max = heap[0];
  40.         heap[0] = heap[lastLeaf];
  41.         fixHeap(0, heap, lastLeaf-1);
  42.         return max;
  43.     }
  44.  
  45.     public static void main(String[] args) {
  46.         Integer[] a = {84,2,7,3,25,14,35,65,88,4};
  47.         System.out.println(java.util.Arrays.toString(a));
  48.         sort(a);
  49.         System.out.println(java.util.Arrays.toString(a));
  50.     }
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement