Benutzer:Mikyra/ Gemeinfrei/ Heap

Der Inhalt des Dokuments ist zusätzlich freigegeben unter WTFPL.

Die Bezeichnung Heap ist ein Sammelbegriff für eine Familie von Datenstrukturen, die eine Reihe ähnlicher Eigenschaften aufweisen. Wird die Bezeichnung Heap ohne weiteren Zusatz verwendet, so ist meist ein binärer Heap gemeint. Es existieren zwei Varianten binärer Heaps, die auch als Min-Heap bzw. Max-Heap bezeichnet werden.

Definition

Ein Max-Heap H ist eine Datenstruktur mit den folgenden Eigenschaften:

(H1) H ist ein vollständiger binärer Baum
(H2) In jedem Knoten n von H ist ein Schlüssel key(n) gespeichert
(H3) H erfüllt die folgende Max Heap Eigenschaft:
Jeder Knoten n mit Elternknoten p erfüllt die Heap-Bedingung: key(p) ≥ key(n)
(H4) H untertsützt die folgenden Operationen:
- (a) insert(key) : Füge den Schlüssel key in H ein
- (b) delete(n) : Entferne den im Knoten n gespeicherten Schlüssel key(n) und liefere ihn zurück
- (c) extract() : Entferne den in der Wurzel des Baums gespeicherten Schlüssel und liefere ihn zurück

Ein Min-Heap unterscheidet sich von einem Max-Heap lediglich in der Eigenschaft (H3). Die Heap-Bedingung lautet hier: key(p) ≤ key(n).

Datenstruktur

Die Eigenschaft (H1) erlaubt es, den binären Baum kompakt zu speichern. Werden die Knoten wie in der nebenstehenden Abbildung fortlaufend nummeriert, so kann jeder Knoten des Baums eindeutig mit einer Zahl i identifiziert werden.

Achtung!! Wie in der Literatur üblich beginnt die Zählung hier ab 1 und nicht wie in C typisch bei 0.

Trotz prinzipieller Wahlfreiheit hält sich die hier vorgestellte Implementierung insbesondere aus folgenden Gründen an den Startwert von 1.

Ein direkter Vergleich mit der Standardliteratur ist möglich
Die Indexberechnung kann übersichtlicher implementiert werden
Zwei der drei Indexberechnungen kommen mit einer Rechenoperation weniger aus

Die Beziehungen, in denen die Knoten zueinander stehen, sind dabei implizit durch die Indices der einzelnen Knoten gegeben. Die Indices von Elternknoten parent(i), linkem Kind left(i) und rechtem Kind right(i) eines Knotens mit Index i können direkt berechnet werden.

Die folgende Tabelle gibt Auskunft über die jeweiligen Berechnungen. Neben der für die Implementierung hier relevanten Spalte links enthält sie exemplarisch eine Spalte für eine Zählung ab 0.

Zählung ab 1	Zählung ab 0
parent(i) = i/2	parent(i) = (i-1)/2
left(i) = 2 * i	left(i) = 2*i + 1
right(i) = 2 * i+1	right(i) = 2*i + 2

Arraydarstellung

Zur Speicherung der in den Knoten von H gespeicherten Schlüssel genügt somit ein Array keys. Neben dem Array keys wird lediglich eine weitere Variable last benötigt, die den aktuellen Füllstand des Baums angibt. In der hier gewählten Implementierung soll sie den Index des letzten belegten Knotens von H angeben.

Die für H benötigten Daten können in C wie folgt in einer Struktur abgelegt werden.

typedef struct {
  int last;
  int *keys;
} Heap;

Bei der Initialisierung dieser Struktur muss auf folgende Punkte geachtet werden.

Der Index last muss auf 0 gesetzt werden
Dem Zeiger keys muss ein Zeiger auf einen Speicherplatz zugewiesen werden, der für die Speicherung der Schlüssel zur Verfügung steht.

Die Zählung der Knoten beginnt bei 1. Auf das Element keys[0] wird somit nie zugegriffen.
Verweist der Zeiger storage auf den für die Speicherung zur Verfügung stehenden Speicherplatz, so kann keys auf storage-1 initialisiert werden.

void heap_init(Heap* h, int* storage) {
   h->last = 0;
   h->keys = storage - 1;
}

Operationen
[Bearbeiten]

Bei der Implementierung der Operationen ist es  an mehreren Stellen nötig, die Schlüssel zweier Knoten miteinander zu vertauschen.
In der Praxis wird dieser Schritt aus Effizienzgründen in der Regel direkt an der jeweiligen Stelle implementiert werden. 
Um den Code möglichst übersichtlich zu halten, wird für das Vertauschen der Schlüssel zweier Knoten m und n hier die folgende Hilfsfunktion verwendet werden.

void swap(Heap* h, int n, int m) {
   int tmp = h->keys[n];
   h->keys[n] = h->keys[m];
   h->keys[m] = tmp;
}

insert(key)
[Bearbeiten]

Animation: insert(key)

Um einen neuen Schlüssel key in H aufnehmen zu können, wird ein weiterer Knoten benötigt.
Ohne die Eigenschaft (H1) zu verletzen, kann hierfür nur der Knoten n mit dem Index last+1 gewählt werden.
Die Heap-Eigenschaft (H3) ist nach dem Einfügen des Knotens genau dann verletzt, wenn der eingefügte Schlüssel größer als der im Elternknoten p von n gespeicherte Schlüssel ist.
In diesem Fall können die Schlüssel von p und n getauscht werden.
Die Heap-Eigenschaft (H3) ist nach dem Tausch genau dann wiederhergestellt, wenn p die Heap-Bedingung erfüllt.
Andernfalls müssen die Schlüssel von p und dem Elternknoten von p getauscht und die Überprüfung beim Elternknoten von p fortgesetzt werden.
Spätestens bei Erreichen der Wurzel ist die Heap-Eigenschaft wiederhergestellt.
Das schrittweise Verschieben des Schlüssels eines Knotens mit Index n in Richtung Wurzel kann in C wie folgt implementiert werden.

void max_heap_bubble_up(Heap* h, int n) {
   int parent;

   while(n > 1) {
      parent = n/2;
      if (h->keys[parent] > h->keys[n])
         break;
      swap(h, parent, n);
      n = parent;
   }
}

Das Einfügen eines Schlüssels key kann mit der Hilfsfunktion max_heap_bubble_up() wie folgt implementiert werden:

void max_heap_insert(Heap* h, int key) {
   h->last += 1;
   h->keys[h->last] = key;

   max_heap_bubble_up(h, h->last);
}

delete(n)
[Bearbeiten]

Animation: delete(key)

Der zu entfernende Schlüssel des Knotens n kann direkt ausgelesen und für die spätere Rückgabe zwischengespeichert werden.
Nach Entfernen des in n gespeicherten Schlüssels wird ein Knoten weniger für die Speicherung der Schlüssel benötigt.
Ohne die Eigenschaft (H1) zu verletzen, kann einzig der Knoten mit dem Index last aus dem Baum entfernt werden.
Der im entfernten Knoten gespeicherte Schlüssel kann im frei gewordenen Knoten gespeichert werden.
Die Heap-Eigenschaft (H3) ist nach dem Umspeichern genau dann verletzt, wenn die Heap-Bedingung für den Knoten n selbst oder für wenigstens einen seiner Kindknoten l und r verletzt ist.
Ist sie für den Knoten n selbst verletzt, so kann der Schlüssel analog zum Einfügen mit der Funktion max_heap_bubble_up() an die richtige Stelle verschoben werden.
Falls wenigstens ein Kindknoten von n die Heap-Bedingung verletzt, so kann der Schlüssel von n mit dem größten Schlüssel der beiden Kindknoten getauscht werden.
Die Heap-Eigenschaft (H3) ist nach dem Tausch genau dann wiederhergestellt, wenn der Kindknoten c, dessen Schlüssel getauscht wurde, die Heap-Bedingung erfüllt.
Andernfalls muss der Schlüssel von c mit dem dem größten Schlüssel seiner beiden Kindknoten getauscht und die Überprüfung beim jeweiligen Kindknoten von c fortgesetzt werden.
Spätestens bei Erreichen eines Blattes ist die Heap-Eigenschaft wiederhergestellt.
Das schrittweise verschieben des Schlüssels eines Knotens mit Index n in Richtung Blätter kann in C wie folgt implementiert werden.

void max_heap_sift_down(Heap* h, int n) {
   int last = h->last;

   while (1) {
      int max   = n;
      int left  = n * 2;
      int right = left + 1;

      if (left <= last && h->keys[left] > h->keys[max])
         max = left;
      if (right <= last && h->keys[right] > h->keys[max])
         max = right;

      if (n == max)
         break;

      swap(h, max, n);

      n = max;
   }
}

Das Entfernen eines im Knoten mit dem Index n gespeicherten Schlüssels kann mit der Hilfsfunktion max_heap_sift_down() wie folgt implementiert werden:

int max_heap_delete(Heap* h, int n) {

   int key = h->keys[n];
   h->keys[n] = h->keys[h->last];
   h->last -= 1;

   if (n >= h->last)
      return key;

   if (n > 1 && h->keys[n] > h->keys[n/2])
      max_heap_bubble_up(h, n);
   else
      max_heap_sift_down(h, n);

   return key;
}

extract()
[Bearbeiten]

Das Entfernen des in der Wurzel gespeicherten Schlüssels ist ein Spezialfall der delete Operation.
Die Operation extract kann somit wie folgt implementiert werden.

int max_heap_extract(Heap* h) {
   return max_heap_delete(h, 1);
}

Laufzeitanalyse
[Bearbeiten]

Ein vollständiger binärer Baum mit N Knoten hat eine Tiefe von log₂(N).
Nach dem Einfügen eines Schlüssels muss dieser im schlimmsten Fall bis zur Wurzel des Baumes verschoben werden.
Die worst-case Laufzeit für die Operation insert(key) beträgt somit O(log N).
Nach dem Entfernen eines Knotens muss der aus dem letzten Knoten übernommene Schlüssel an die richtige Position verschoben werden.
Unabhängig davon, ob er zunächst in Richtung Wurzel oder in Richtung Blätter verschoben werden muss, behält er diese Richtung solange bei, bis er an die richtige Position verschoben wurde. Im schlimmsten Fall muss er hierbei die gesamte Tiefe des Baumes durchwandern.
Die worst-case Laufzeit für die Operation delete(n) beträgt somit O(log N).

Quellcode
[Bearbeiten]

Zwecks besserer Übersicht hier der vollständige Quellcode der Implementierung am Stück.
Neben der dargestellten Implementierung eines Max-Heap, enthält sie zudem die analoge Implementierung eines Min-Heap.

/* COMMON ------------------------------------------------------------------ */

typedef struct {
   int last;
   int* keys;
} Heap;

void swap(Heap* h, int n, int m) {
   int tmp = h->keys[n];
   h->keys[n] = h->keys[m];
   h->keys[m] = tmp;
}

void heap_init(Heap* h, int* storage) {
   h->last = 0;
   h->keys = storage - 1;
}

/* MAX-HEAP ---------------------------------------------------------------- */

static void max_heap_bubble_up(Heap* h, int n) {
   int parent;

   while(n > 1) {
      parent = n/2;
      if (h->keys[parent] > h->keys[n])
         break;
      swap(h, parent, n);
      n = parent;
   }
}

void max_heap_insert(Heap* h, int key) {
   h->last += 1;
   h->keys[h->last] = key;

   max_heap_bubble_up(h, h->last);
}

static void max_heap_sift_down(Heap* h, int n) {
   int last = h->last;

   while (1) {
      int max   = n;
      int left  = n * 2;
      int right = left + 1;

      if (left <= last && h->keys[left] > h->keys[max])
         max = left;
      if (right <= last && h->keys[right] > h->keys[max])
         max = right;

      if (n == max)
         break;

      swap(h, max, n);
      n = max;
   }
}

int max_heap_delete(Heap* h, int n) {

   int key = h->keys[n];
   h->keys[n] = h->keys[h->last];
   h->last -= 1;

   if (n >= h->last)
      return key;

   if (n > 1 && h->keys[n] > h->keys[n/2])
      max_heap_bubble_up(h, n);
   else
      max_heap_sift_down(h, n);

   return key;
}

int max_heap_extract(Heap* h) {
   return max_heap_delete(h, 1);
}

/* MIN-HEAP ---------------------------------------------------------------- */

static void min_heap_bubble_up(Heap* h, int n) {
   int parent;

   while(n > 1) {
      parent = n/2;
      if (h->keys[parent] < h->keys[n])
         break;
      swap(h, parent, n);
      n = parent;
   }
}

void min_heap_insert(Heap* h, int key) {
   h->last += 1;
   h->keys[h->last] = key;

   min_heap_bubble_up(h, h->last);
}

static void min_heap_sift_down(Heap* h, int n) {
   int last = h->last;

   while (1) {
      int min   = n;
      int left  = n * 2;
      int right = left + 1;

      if (left <= last && h->keys[left] < h->keys[min])
         min = left;
      if (right <= last && h->keys[right] < h->keys[min])
         min = right;

      if (n == min)
         break;

      swap(h, min, n);
      n = min;
   }
}

int min_heap_delete(Heap* h, int n) {

   int key = h->keys[n];
   h->keys[n] = h->keys[h->last];
   h->last -= 1;

   if (n >= h->last)
      return key;

   if (n > 1 && h->keys[n] < h->keys[n/2])
      min_heap_bubble_up(h, n);
   else
      min_heap_sift_down(h, n);

   return key;
}

int min_heap_extract(Heap* h) {
   return min_heap_delete(h, 1);
}