Heap nach oben verschieben

In diesem Abschnitt wird gezeigt, wie man einem Max-Heap ein Element hinzufügt, genanntshift up。

Angenommen, wir fügen dem untenstehenden Max-Heap ein neues Element 52 hinzu und platzieren es an der letzten Position des Arrays. Da 52 größer als sein Elternknoten 16 ist, ist die Heap-Eigenschaft nicht erfüllt, und eine Anpassung ist erforderlich.

Zuerst werden die Werte an den Indizes 5 und 11 im Array vertauscht, das heißt, 52 und 16 werden vertauscht.

An diesem Punkt ist 52 immer noch größer als der Wert 41 am Elternindex 2, also müssen wir es weiter nach oben verschieben.

Vergleichen wir nun 52 mit 62. Da 52 bereits kleiner als sein Elternknoten ist, muss es nicht weiter nach oben verschoben werden, und die Max-Heap-Eigenschaft ist erfüllt. Wir nennen diesen Vorgang shift up für einen Max-Heap.

Java-Beispielcode

Quellcode-Paket-Download:Download

src/example/heap/HeapShiftUp.java Dateicode:

package example.heap;

/**
* Ein Element zum Heap hinzufügen
 */

public class HeapShiftUp<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Konstruktor, erzeugt einen leeren Heap, der capacity Elemente aufnehmen kann
    public HeapShiftUp(int capacity){
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // Gibt die Anzahl der Elemente im Heap zurück
    public int size(){
        return count;
    }

    // Gibt einen booleschen Wert zurück, der angibt, ob der Heap leer ist
    public boolean isEmpty(){
        return count == 0;
    }
    // Ein neues Element item in den Max-Heap einfügen
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Die beiden Elemente an den Indizes i und j im Heap vertauschen
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Kern-Hilfsfunktionen für den Max-Heap
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    // Test HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // Anzahl der Elemente im Heap
        int M = 100; // Wertebereich der Heap-Elemente [0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
Weitere Erweiterungen