Heap nach unten verschieben
In diesem Abschnitt wird erläutert, wie ein Element aus einem Max-Heap entnommen wird, was als Shift-down bezeichnet wird. Nur das Element mit der höchsten Priorität kann entnommen werden, nämlich der Wurzelknoten. Nachdem das ursprüngliche 62 entnommen wurde, wird im Folgenden erklärt, wie dieser Max-Heap wieder aufgefüllt wird.

Der erste Schritt besteht darin, das letzte Element des Arrays am Wurzelknoten zu platzieren. Zu diesem Zeitpunkt erfüllt es nicht die Definition eines Max-Heaps.

Der Anpassungsprozess besteht darin, diesen Wurzelknoten 16 schrittweise nach unten zu verschieben. Da 16 kleiner als beide Kindknoten ist, werden zuerst die Kindknoten 52 und 30 verglichen, um festzustellen, welcher größer ist, und die Positionen mit dem größeren getauscht.

Vergleichen Sie weiterhin die Kindknoten 28 und 41 von 16. Da 41 größer ist, tauschen 16 und 41 die Positionen.

Vergleichen Sie weiterhin 16 mit seinem Kindknoten 15. Da 16 größer ist, ist jetzt kein Tausch erforderlich. Schließlich ist unsere Shift-down-Operation abgeschlossen, wodurch die Eigenschaft eines Max-Heaps erhalten bleibt.
4. Java-Beispielcode
Quellpaket-Download:Herunterladen
Code der Datei src/example/heap/HeapShiftDown.java:
/**
* Extrahiere ein Element aus dem Max-Heap
*/
public class HeapShiftDown<T extends Comparable> {
protected T[] data;
protected int count;
protected int capacity;
// Konstruktor, erzeugt einen leeren Heap, der capacity Elemente aufnehmen kann
public HeapShiftDown(int capacity){
// Das +1 hier bezieht sich auf die Anzahl der Elemente, die ursprünglich gespeichert werden können; nach dem Entfernen der 0. Position kann sie nur capacity Elemente aufnehmen
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);
}
// Das oberste Element aus dem Max-Heap entnehmen, d. h. das größte im Heap gespeicherte Datenelement
public T extractMax(){
assert count > 0;
T ret = data[1];
swap( 1 , count );
count --;
shiftDown(1);
return ret;
}
// Oberstes Element des Max-Heaps abrufen
public T getMax(){
assert( count > 0 );
return data[1];
}
// 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;
}
}
// shiftDown-Operation
private void shiftDown(int k){
while( 2*k <= count ){
int j = 2*k; // In dieser Schleifeniteration tauschen data[k] und data[j] die Positionen
if( j+1 <= count && data[j+1].compareTo(data[j]) > 0 )
j ++;
// data[j] ist das Maximum von data[2*k] und data[2*k+1]
if( data[k].compareTo(data[j]) >= 0 ) break;
swap(k, j);
k = j;
}
System.out.println("shiftDown beendet");
}
// Test für HeapShiftDown
public static void main(String[] args) {
HeapShiftDown<Integer> heapShiftDown = new HeapShiftDown<Integer>(100);
// Anzahl der Elemente im Heap
int N = 100;
// Wertebereich der Heap-Elemente [0, M)
int M = 100;
for( int i = 0 ; i < N ; i ++ )
heapShiftDown.insert( new Integer((int)(Math.random() * M)) );
Integer[] arr = new Integer[N];
// Daten schrittweise mit extractMax aus dem Max-Heap extrahieren
// Die Entnahmereihenfolge sollte absteigend sein
for( int i = 0 ; i < N ; i ++ ){
arr[i] = heapShiftDown.extractMax();
System.out.print(arr[i] + " ");
}
// Sicherstellen, dass das arr-Array absteigend sortiert ist
for( int i = 1 ; i < N ; i ++ )
assert arr[i-1] >= arr[i];
}
}