Salve, devo trasformare questo Heap(array) in un Heap(liste), avete qualche idea?
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));
}
}