Grundlegende Speicherung des Heaps

Konzept und Einführung

Heap ist ein Oberbegriff für eine spezielle Klasse von Datenstrukturen in der Informatik.

Ein Heap ist üblicherweise ein Array-Objekt, das als vollständiger Binärbaum betrachtet werden kann.

Ein Heap erfüllt die folgenden Eigenschaften:

  • Der Wert eines Knotens in einem Heap ist stets entweder nicht größer als oder nicht kleiner als der Wert seines Elternknotens.
  • Ein Heap ist immer ein vollständiger Binärbaum.

II. Hinweise zur Anwendbarkeit

Ein Heap verwendet die Struktur eines vollständigen Binärbaums, um eine Datenmenge zu verwalten und dann zugehörige Operationen auszuführen. Die Zeitkomplexität einer typischen Operation beträgtO(1)~O(logn)Gleichzeitig werden Heaps häufig verwendet, um von Programmen genutzte Objekte dynamisch zuzuweisen und freizugeben.

Für ein Einsatzszenario mit einer Prioritätswarteschlange ist bei einem normalen Array oder einem geordneten Array der Worst CaseO(n^2)dass die Heap-Datenstruktur auch die Effizienz von Enqueue- und Dequeue-Operationen verbessern kann.

 EinreihenEntnehmen
Normales ArrayO(1)O(n)
Sortiertes ArrayO(n)O(1)
HeapO(logn)O(log)

III. Strukturdiagramm

Ein Binärheap ist ein vollständiger Binärbaum, und der Wert eines Knotens im Heap ist immer nicht größer als der Wert seines Elternknotens. Die Tiefe des vollständigen Binärbaums ist k. Mit Ausnahme der k-ten Ebene erreicht die Anzahl der Knoten auf allen anderen Ebenen (1 bis k-1) das Maximum, und alle Knoten auf der k-ten Ebene sind durchgehend am linken Rand konzentriert.

Der Heap, dessen Wurzelknoten der größte ist, wird als Max-Heap bezeichnet, wie in der folgenden Abbildung gezeigt:

Wir können ein Array verwenden, um den Binärheap zu speichern; die Beschriftungen auf der rechten Seite sind die Indizes des Arrays.

Angenommen, die Indexposition des aktuellen Elements ist i, dann können wir die Regel ableiten:

parent(i) = i/2（取整）
left child(i) = 2*i
right child(i) = 2*i +1

IV. Java-Beispielcode

Quellcode-Paket-Download:Download

Code der Datei src/example/heap/MaxHeap.java:

package example.heap;

/**
* Heap-Definition
 */
public class MaxHeap<T> {
    private T[] data;
    private int count;
    // Konstruktor, erzeugt einen leeren Heap, der capacity Elemente aufnehmen kann
    public MaxHeap(int capacity){
        data = (T[])new Object[capacity+1];
        count = 0;
    }
    // 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;
    }
    // MaxHeap testen
    public static void main(String[] args) {
        MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
        System.out.println(maxHeap.size());
    }
}
Weitere Erweiterungen