Min-Heapify-Methode - Min-heap-Algorithmus

Ich versuche zu bauen, ein min-heap. Habe ich bereits getan, einfügen, löschen,tauschen, bis heap, nach unten heap, und es arbeitet richtig.

Allerdings bin ich zu schreiben versucht, eine Methode die für Min-Heapify.

Hier mein Input: {20,14,9,6,4,5,1}

Die Ausgabe, die ich erwartet, wäre für die min-heap: {1,5,4,20,9,6,14}
Aber Was ich bekam ist : {14,6,9,20,4,5,1}, ist das Gegenteil.

Hier ist mein code:

public void minHeapify(int parentIndex)
    {
        int left = getLeft(parentIndex);
        int right = getRight(parentIndex);
        int smallest = parentIndex;
        if(_size >right && _heapArray[left]<_heapArray[parentIndex])
        {
            smallest = left;
        }

        if(_size>left && _heapArray[right]<_heapArray[parentIndex])
        {
            smallest = right;
        }
        if(smallest !=parentIndex)
        {
            replace(parentIndex, smallest);
            minHeapify(smallest);
        }
    }

Folgte ich dieser pseudocode für die MAX-Heapify

Heapify (A, i)
l ← left [i]
r ← right [i]
if l ≤ heap-size [A] and A[l] > A[i]
then largest ← l
else largest ← i
if r ≤ heap-size [A] and A[i] > A[largest]
then largest ← r
if largest  ≠ i
then exchange A[i] ↔ A[largest]
Heapify (A, largest)

InformationsquelleAutor COLD ICE | 2013-03-19