Devo trasformare questo Heap in array in un Heap in lista

di il
1 risposte

Devo trasformare questo Heap in array in un Heap in lista

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));
    }
}

1 Risposte

  • Re: Devo trasformare questo Heap in array in un Heap in lista

    CarloMassone ha scritto:


    Salve, devo trasformare questo Heap(array) in un Heap(liste), avete qualche idea?
    Allora, come "base" iniziale, sicuramente i parametri invece che T[] array saranno List<T> list
    Per settare/leggere un elemento si dovranno ovviamente poi usare i metodi set e get. Se fai queste modifiche "tecniche", la tua implementazione di per sé funziona esattamente come sull'array. Non è quello il difficile.

    Solo che .... se riceve un List (la interfaccia), può ricevere qualunque implementazione di List, compreso es. un LinkedList. Se la lista non è ad accesso "casuale" (e LinkedList infatti non lo è), accedere ad un elemento i-esimo è inefficiente. Se ci sono solo una manciata di valori in gioco, come nel tuo main, chiaramente non è un problema rilevante.
Devi accedere o registrarti per scrivere nel forum
1 risposte