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:
/**
* 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());
}
}