Wie funktionieren Heaps?

Heaps oder Heaps sind eine baumartige Datenstruktur, die speziell entwickelt wurde, um einen schnellen Zugriff auf das „maximale“ oder „minimale“ Element eines Datensatzes zu gewährleisten. Diese werden hauptsächlich in zwei Typen eingeteilt: Max-Heaps und Min-Heaps. Bei einem Max-Heap befindet sich der Maximalwert an der Wurzel des Baums und kann daher in konstanter Zeit abgerufen werden, während bei einem Min-Heap der Minimalwert die Wurzel einnimmt.

Die Heap-Struktur stellt sicher, dass für jeden Knoten \( i \) außer der Wurzel der Wert des Knotens \( i \) größer (in einem Max-Heap) oder kleiner (in einem Min-Heap) ist als den Wert seines übergeordneten Knotens. Diese Eigenschaft macht Heaps für effiziente Implementierungen von Prioritätswarteschlangen nützlich.

Der Betrieb von Heaps basiert auf Hauptoperationen wie dem Einfügen und Extrahieren des Maximums (oder Minimums). Das Einfügen erfolgt durch Hinzufügen des neuen Elements am Ende des Baums (wobei die vollständige Form des Baums beibehalten wird) und anschließendes Durchführen einer „Heraufstufen“-Operation, bei der das eingefügte Element mit seinem übergeordneten Knoten verglichen und bei Bedarf ausgetauscht wird, bis es erreicht ist ist Sie setzen die Heap-Eigenschaften zurück.

Funktion insert(value, heap) {
     heap.push(Wert);
     siftUp(heap.length - 1, heap);
}

Funktion siftUp(index, heap) {
     let parentIndex = Math.floor((index - 1) / 2);
     while (index > 0 && heap[parentIndex] < heap[index]) {
         swap(index, parentIndex, heap);
         index = parentIndex;
         parentIndex = Math.floor((index - 1) / 2);
     }
}

Das Entfernen des Maximums (oder Minimums) erfolgt durch Entfernen der Wurzel des Baums, anschließendes Verschieben des letzten Elements des Baums zur Wurzel und schließlich Durchführen einer „Abstiegs“-Operation, bei der dieses Element mit seinen untergeordneten Elementen verglichen und ausgetauscht wird Die Heap-Eigenschaften werden zurückgesetzt.

Funktion extractMax(heap) {
     const max = heap[0];
     heap[0] = heap.pop();
     siftDown(0, Heap);
     Rückkehr max;
}

Funktion siftDown(index, heap) {
     let leftChildIndex = 2 * index + 1;
     let rightChildIndex = 2 * index + 2;
     let most = index;

     if (leftChildIndex < heap.length && heap[leftChildIndex] > heap[largest]) {
         größter = leftChildIndex;
     }
     if (rightChildIndex < heap.length && heap[rightChildIndex] > heap[largest]) {
         größter = rightChildIndex;
     }
     if (größter !== Index) {
         swap(index, most, heap);
         siftDown(largest, heap);
     }
}

Dank dieser Operationen sind Heaps äußerst nützlich in Anwendungen, die einen schnellen und wiederholten Zugriff auf die größten oder kleinsten Elemente erfordern, wie z. B. Algorithmen zur Auswahl der k-ten Elemente, diskrete Ereignissimulation und mehr.