Heap

Ein Heap ist eine spezielle Baum-Datenstruktur, die bestimmte Eigenschaften aufweist, die sie besonders effizient für bestimmte Algorithmen machen, wie zum Beispiel Priority Queues. Es gibt zwei Hauptarten von Heaps: Min-Heaps und Max-Heaps.

Hauptmerkmale eines Heaps

1. Binäre Baumstruktur: Heaps sind Binärbäume, bei denen jedes Elternknoten maximal zwei Kindknoten hat.
2. Heap-Eigenschaft:
   • Min-Heap: Der Wert jedes Elternknotens ist kleiner oder gleich dem Wert seiner Kindknoten. Das kleinste Element befindet sich somit an der Wurzel.
   • Max-Heap: Der Wert jedes Elternknotens ist größer oder gleich dem Wert seiner Kindknoten. Das größte Element befindet sich somit an der Wurzel.

Anwendungsfälle

1. Priority Queues: Heaps sind ideal für die Implementierung von Prioritätswarteschlangen, bei denen das Element mit der höchsten Priorität (größter oder kleinster Wert) effizient entfernt werden kann.
2. Heapsort: Ein effizienter Vergleichs-Sortieralgorithmus, der die Heap-Eigenschaften nutzt.
3. Dijkstra’s Algorithmus: Verwendet Heaps zur effizienten Berechnung der kürzesten Wege in einem Graphen.

Operationen auf einem Heap

1. Einfügen (Insert): Ein neues Element wird am Ende des Heaps hinzugefügt und dann "hochgeschoben" (percolate up), bis die Heap-Eigenschaft wiederhergestellt ist.
2. Entfernen des Wurzelelements (Remove): Das Wurzelelement wird entfernt, und das letzte Element im Heap wird an die Wurzel verschoben und "heruntergeschoben" (percolate down), bis die Heap-Eigenschaft wiederhergestellt ist.
3. Peek: Rückgabe des Wertes an der Wurzel ohne Entfernung.

Beispiel in PHP

Hier ist ein einfaches Beispiel für die Implementierung eines Min-Heaps in PHP:

class MinHeap {
    private $heap;

    public function __construct() {
        $this->heap = [];
    }

    public function insert($value) {
        $this->heap[] = $value;
        $this->percolateUp(count($this->heap) - 1);
    }

    public function extractMin() {
        if (count($this->heap) === 0) {
            return null; // Heap is empty
        }

        $min = $this->heap[0];
        $this->heap[0] = array_pop($this->heap);
        $this->percolateDown(0);

        return $min;
    }

    private function percolateUp($index) {
        while ($index > 0) {
            $parentIndex = intdiv($index - 1, 2);

            if ($this->heap[$index] >= $this->heap[$parentIndex]) {
                break;
            }

            $this->swap($index, $parentIndex);
            $index = $parentIndex;
        }
    }

    private function percolateDown($index) {
        $lastIndex = count($this->heap) - 1;

        while (true) {
            $leftChild = 2 * $index + 1;
            $rightChild = 2 * $index + 2;
            $smallest = $index;

            if ($leftChild <= $lastIndex && $this->heap[$leftChild] < $this->heap[$smallest]) {
                $smallest = $leftChild;
            }

            if ($rightChild <= $lastIndex && $this->heap[$rightChild] < $this->heap[$smallest]) {
                $smallest = $rightChild;
            }

            if ($smallest === $index) {
                break;
            }

            $this->swap($index, $smallest);
            $index = $smallest;
        }
    }

    private function swap($index1, $index2) {
        $temp = $this->heap[$index1];
        $this->heap[$index1] = $this->heap[$index2];
        $this->heap[$index2] = $temp;
    }
}

// Example usage
$heap = new MinHeap();
$heap->insert(5);
$heap->insert(3);
$heap->insert(8);
$heap->insert(1);

echo $heap->extractMin(); // Output: 1
echo $heap->extractMin(); // Output: 3
echo $heap->extractMin(); // Output: 5
echo $heap->extractMin(); // Output: 8

In diesem Beispiel wird ein Min-Heap implementiert, bei dem die kleinsten Elemente zuerst extrahiert werden. Die Methoden insert und extractMin sorgen dafür, dass die Heap-Eigenschaften nach jeder Operation erhalten bleiben.