Matroids Matheplanet Forum Index
Forumbereich moderiert von: matroid
Informatik » Algorithmen / Datenstrukturen » MinHeap-ALG
Druckversion
Druckversion
Universität/Hochschule J MinHeap-ALG
ProfSnape Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 12.10.2019, Mitteilungen: 48
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Themenstart: 2020-11-21 10:20

Hi!

In der Vorlesung haben wir den maxHeap-Sort-ALG besprochen.
Nun wollte ich mich an dem selben ALG versuchen, nur eben ausgehend aus einer gebauten Min-Heap-Datenstruktur, d.h. in jedem Heapify-Durchgang wird an die Wurzel das kleinste Element gesetzt.
Leider "ersiche" ich so nicht alle Knoten und frage mich, wie ich es richtig machen kann - orientiert habe ich mich an den Code für den maxHeap aus der Vorlesung - hier in Java (nicht objektorientiert, weil das hier nicht erwünscht ist)  :
Java
public class HeapSort {
    public static void main(String[] args) {
        int[] array = {5, 3, 1, 2, 6, 4};
       // int[] array = {34, 45, 12, 34, 23, 18, 38, 17, 43, 51};
       // int[] array = { 2,4,9,18,21,37};
 
        int first = 0;
        int last = array.length-1;
 
        heapSort(array, first, last);
        for(int i = 0; i < array.length; i++) {
            if(i == array.length - 1) {
                System.out.println(array[i]);
                break;
            }
            System.out.print(array[i] + ", ");
        }
    }
 
    private static void heapSort(int[] arr, int first, int last) {
        buildHeap(arr, first, last);
 
        for(int i = last; i > first; i--) {
            swap(arr, first, i);
            heapify(arr, first, i - 1, first); // (i - 1) -> "new Last" after swap
        }
    }
 
    private static void buildHeap(int[] arr, int first, int last) {
        int n = last - first + 1; // current last = (n - 1)
        for(int i = first + (n-2)/2; i >= first; i--) { // the 1st 'first' can be potentially cut off / reduced
            heapify(arr, first, last, i); // i will be considered as current root
        }
    }
 
    private static void heapify(int[] arr, int first, int last, int root) {
        int largest;
        int left = first + 2*(root - first) + 1, right = first + 2*(root - first) + 2;
 
        if(left <= last && arr[left] > arr[root]) {
            largest = left;
        } else {
            largest = root;
        }
 
        if(right <= last && arr[right] > arr[largest]) {
            largest = right;
        }
 
        if(largest != root) {
            swap(arr, root, largest); // the values get swapped, but the indices stay the same.
            heapify(arr, first, last, largest);
        }
    }
 
    private static void swap(int [] arr, int rootPos, int largestPos) {
        int temp = arr[rootPos];
        arr[rootPos] = arr[largestPos];
        arr[largestPos] = temp;
    }
}
 

Nun mein erster Versuch einen Min-Heap zum Sortieren zu basteln:
Java
public class HeapSortMin {
 
    public static void main(String[] args) {
        int[] array = {5, 3, 1, 2, 6, 4};
        // int[] array = {34, 45, 12, 34, 23, 18, 38, 17, 43, 51};
        // int[] array = { 2,4,9,18,21,37};
 
        int first = 0;
        int last = array.length-1;
 
        heapSort(array, first, last);
        for(int i = 0; i < array.length; i++) {
            if(i == array.length - 1) {
                System.out.println(array[i]);
                break;
            }
            System.out.print(array[i] + ", ");
        }
    }
 
    //-------------------------------logic----------------------------------
 
    public static void heapSort(int[] a, int first, int last) {
        buildHeap(a, first, last);
 
        for(int i = first; i < last; i++) {
            heapify(a, i+1, last,i+1);
        }
    }
 
    public static void buildHeap(int[] a, int first, int last) {
        int n = last - first + 1;
        for(int i = first + (n-2)/2; i >= first; i--) {
            heapify(a, first, last, i);
        }
    }
 
    public static void heapify(int[] a, int first, int last, int root) {
        int smallest;
        int left = 2 * (root) + 1;
        int right = 2 * (root) + 2;
 
        if(left <= last && a[left] < a[root]) {
            smallest = left;
        } else {
            smallest = root;
        }
 
        if(right <= last && a[right] < a[smallest]) {
            smallest = right;
        }
 
        if(smallest != root) {
            swap(a, root, smallest);
            heapify(a, first, last, smallest); // wird nur rekursiv aufgerufen, wenn root != smallest
        }
 
 
    }
       // helper method
    public static void swap(int[] a, int root, int smallest) {
        int temp = a[root];
        a[root] = a[smallest];
        a[smallest] = temp;
    }
}
 

Ich sehe im Debugger, dass ich eben in der Hauptmethode heapSort() bei meinen heapify()-Aufrufen nicht alle Knoten "erwische", aber ich weiß nicht, wie das Problem zu lösen ist...

Ist denn meine Grundidee zum minHeap überhaupt korrekt?
- An die current_Wurzel immer den kleinsten Wert bringen.
- In jedem weiterem heapify-Aufruf soll nun aber das erste Element eine Position weiter rechts sein (also Beginn eins weiter), weil ja die vorherige Position mit der vorherigen Wurzel , d.h. mit dem ehemals kleinstem Wert aus dem dortigem Teilbaum bereits korrekt belegt/einsortiert ist.

                          Ist der Grundgedanke korrekt?
Über Hilfe bin ich wie immer dankbar^^

Lg
ProfSnape



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Scynja Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 23.02.2011, Mitteilungen: 353
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.1, eingetragen 2020-11-21 23:02

Hallo ProfSnape,
für heapmin kannst du den ersten Algorithmus nehmen und > durch < an beiden Stellen (nach dem "<=") ersetzen.

Dann kannst du deinen Algorithmus mit der Musterlösung vergleichen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape Aktiv Letzter Besuch: in der letzten Woche
Mitglied seit: 12.10.2019, Mitteilungen: 48
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum ersten Beitrag
Beitrag No.2, vom Themenstarter, eingetragen 2020-11-22 13:02

Oh, Tatsache - das wars ja schon - vielen Dank!:)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
ProfSnape hat die Antworten auf ihre/seine Frage gesehen.
ProfSnape hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]