Heap-Sort erstellen

[GaanSan]

Hallo, ich versuche mich gerade mit Heap-Sort anzufreunden aber irgendwie verstehe ich nicht alles und komme einfach nicht weiter.

Kann mir vielleicht jemand helfen, und sagen wie ich einen Heap aus gespeicherten Daten (z.B: daten[12, 7, 1, 22, 3, ...] ) erstelle?

Danke im Vorraus

Gz Gaan

 

[takidoso]

Ich bin zwar nicht der große Sortier Experte, aber schau doch mal hier drauf

 

[Thomas Darimont]

Hallo,

schau mal hier:

package de.tutorials;

import java.util.Arrays;

public class HeapSortExample {

    /**
     * @param args
     */
    public static void main(String[] args) {
        Heap heap = new Heap(57, 16, 62,1000, 30, 80, 7, 21, 78, 41);
        System.out.println(heap);
        System.out.println(heap.sort());

    }

    static class Heap {

        int[] a;

        public Heap(int... values) {
            this.a = values;
        }

        public Heap sort() {

            for (int i = a.length / 2; i >= 0; i--) {
                sink(i, a.length-1);
            }

            for (int m = a.length - 1; m > 0; m--) {

                int tmp = a[0];
                a[0] = a[m];
                a[m] = tmp;

                sink(0, m - 1);
            }

            return this;
        }

        private void sink(int i, int t) {
            int j = 2 * i;
            int k = j + 1;

            if (j <= t) {
                if (a[i] >= a[j]) {
                    j = i;
                }
                
                if (k <= t) {
                    if (a[k] > a[j]) {
                        j = k;
                    }
                }

                if (i != j) {

                    int tmp = a[i];
                    a[i] = a[j];
                    a[j] = tmp;

                    sink(j, t);
                }
            }
        }

        @Override
        public String toString() {
            return Arrays.toString(a);
        }

    }

}

Ausgabe:

[57, 16, 62, 1000, 30, 80, 7, 21, 78, 41]
[7, 16, 21, 30, 41, 57, 62, 78, 80, 1000]

Gruß Tom

 

[b-tyl]

Hallo ,

Ich hab da auch mal ne Frage, wie kann man denn zb in so ein Heap Sort Elemente Einfügen bzw Entfernen, wenn man davon ausgeht, dass das Minimum in der Wurzel ist.


Danke im Voraus auf eine Antwort.

Viele Grüße

Btyl