In diesem Artikel geht es darum, was genau ein „Heap“ (im Bezug auf Datenstrukturen) ist und wie er implementiert wird. „Heap“ bedeutet frei aus dem Englischen übersetzt nichts anderes als „Haufen“. Allerdings werden wir unsere Daten nicht einfach nur auf einen Haufen werfen, ein „Heap“ funktioniert grundlegend nach dem Prinzip von binären Bäumen. Was das im Einzelnen heißt, werden wir nun lernen.

Die Datenstruktur, die Thema dieses Artikels ist, ist nicht mit dem „Heap“ als Speicherbereich oder dem „Heap“ im Sinne der Garbage Collection zu verwechseln. Es handelt sich um eine Datenstruktur, mit deren Hilfe eine Menge an Daten in einer quasi-geordneten Reihenfolge gehalten werden kann.

Ein Heap ist im Grunde genommen nichts anderes als ein spezieller binärer Baum. Wir haben also Knoten, die jeweils bis zu 2 Kindknoten haben können. Jeder Knoten trägt eine Dateneinheit aus der Menge aller gespeicherten Daten im Heap. Alle Ebenen des Baums sind zu jedem Zeitpunkt voll aufgefüllt, mit Ausnahme der untersten Ebene, sie wird von links nach rechts aufgefüllt und kann daher auch nur teilweise gefüllt sein.

Technisch könnte das also durch eine Datenstruktur HeapNode realisiert werden, die 3 (2 Kinder-, 1 Elternknoten) Zeiger auf weitere HeapNode enthält. Alternativ lässt sich ein Heap auch (sozusagen „flach“) in ein Array packen. Dabei werden die Elemente einer Ebene einfach von links nach rechts in ein Array gepackt, beginnend bei der obersten Ebene. Beide Möglichkeiten haben ihre Vor- und Nachteile:

Vorteile der Lösung mit einer „echten Baumstruktur“:

• Es kann eine beliebige Menge an Daten verwaltet werden.
• Dateneinheiten müssen nicht im Speicher verschoben werden, es werden lediglich Zeiger verändert.

Nachteile:

• Zur Speicherung der Zeiger ist zusätzlicher Speicherplatz nötig.

Vorteile der Alternativlösung „im Array“:

• Sämtlicher für den Heap angeforderter Speicher kann für Daten verwendet werden, es sind keine Extra-Informationen zu speichern.
• Es sind keine „komplizierten“ (das ist abhängig von den Fähigkeiten des Programmierers) Operationen mit Zeigern nötig.

Nachteile:

• Die Menge an zu verwaltenden Daten ist vorher exakt festgeschrieben. (Es gibt auch Möglichkeiten diese Beschränkung zu umgehen, allerdings ist dies nicht gerade effektiv)
• Die Dateneinheiten werden innerhalb des Arrays oft hin und her kopiert. (Auch das kann - mit Hilfe von Zeigern/Referenzen - umgangen werden)

Wir werden in diesem Artikel auf beide Möglichkeiten eingehen, um an den entsprechenden Stellen die Unterschiede auch deutlich aufzeigen zu können. Das Grundprinzip hinter beiden Implementationen bleibt allerdings das Gleiche. Um beide Implementationen besser auseinander halten zu können, werden wir sie farbig markieren. Die Implementierung über eine echte Baumstruktur wird rot, die Alternativimplementation in einem Array blau markiert.

Für die Implementation mit echter Baumstruktur sollten wir uns eine Datenstruktur als Knoten (engl. Node) definieren.

/*
 * Die Datenstruktur für einen Knoten im Baum.
*/
struct HeapNode
{
    /*
     * Eine Dateneinheit, hier vom Typ Integer.
    */
    int data;
 
    /*
     * Zeiger auf das linke und das rechte Kind sowie auf den Elternknoten.
    */
    struct HeapNode* left;
    struct HeapNode* right;
    struct HeapNode* parent;
};
 
/*
 * Die Datenstruktur für den Heap.
*/
struct Heap
{
    /*
     * Zeiger auf die Wurzel, also den obersten Knoten im Baum.
    */
    struct HeapNode* root;
    struct HeapNode* last_node;
 
    /*
     * Einstellen der Heap-Eigenschaft. (wird gleich erklärt)
    */
    short factor;
};

Bei der Implementation in einem Array müssen wir eine feste Größe des Heaps angeben. Der Zugriff auf das „linke“ und das „rechte“ Kind bzw. auf den „Elternknoten“ erfolgt hier durch Berechnung des Indizes des jeweiligen Elements. Diese Berechnung zu verstehen ist wichtig um den Gedanken hinter dieser Implementation zu begreifen!

Wenn der Index des aktuellen Elements i ist, dann befindet sich das linke Kind an (2*i) und das rechte an (2*i + 1). Daraus folgt auch die Berechnung des Elternknoten: Er hat den Index (i/2). Der Index wird hierbei von 1 an gezählt! Bei der Implementierung muss entsprechend umgerechnet werden.

/*
 * Definition einer festen Größe für den Heap.
*/
#define HEAP_SIZE 15
 
/*
 * Die Datenstruktur für den Heap.
*/
struct Heap
{
    /*
     * Array fester Größe, in das die Daten (hier vom Typ Integer) geschrieben werden.
    */
    int data[HEAP_SIZE];
 
    /*
     * Aktuelle Größe des Heaps.
    */
    int size;
 
    /*
     * Einstellen der Heap-Eigenschaft. (wird gleich erklärt)
    */
    short factor;
};

Bis jetzt unterscheidet sich unser Heap nicht sehr von einem binären Baum. Das ändert sich mit Betrachtung der sogenannten „Heap-Eigenschaft“. Durch den Erhalt dieser Eigenschaft behält der Heap seine „Quasi-Sortierung“.

Die Heap-Eigenschaft kann unterschiedlich formuliert werden, je nach Aufgabenstellung des Heaps. Interessiert man sich eher für das Maximum der Elemente im Heap, so formuliert man eine Max-Heap-Eigenschaft. Ist das Minimum von Interesse, dann ist die Min-Heap-Eigenschaft von Nützen.

„Ein Heap hat die Max-Heap-Eigenschaft, wenn der Elternknoten jedes Knotens einen größeren Wert als der Knoten selbst hat.“

Konkret bedeutet das, dass jeder Knoten im Baum, der „unter“ einem anderen steht, auf jeden Fall einen kleineren Wert als dieser Knoten hat. Analog dazu ist die Min-Heap-Eigenschaft formuliert:

„Ein Heap hat die Min-Heap-Eigenschaft, wenn der Elternknoten jedes Knotens einen kleineren Wert als der Knoten selbst hat.“

Unsere Implementierungen werden wir so zusammenbauen, dass sie sowohl die eine, als auch die andere Eigenschaft erfüllen können. (Natürlich nicht gleichzeitig ^^ sondern je nach Anforderung). Hierfür steht auch das Attribut „factor“ in den jeweiligen Strukturen. Ein Wert von 1 deutet auf einen Heap mit der Max-Heap-Eigenschaft hin, ein Wert von -1 auf die Min-Heap-Eigenschaft.

/*
 * Definitionen zur Unterscheidung von Min/Max-Heaps.
*/
#define HEAP_TYPE_MAX (1)
#define HEAP_TYPE_MIN (-1)

Wir werden die Werte der einzelnen Knoten vor dem Vergleichen (und damit der Entscheidung, wo sie eingeordnet werden) mit dem obigen Faktor multiplizieren. So sparen wir uns den Mehraufwand an Programmierarbeit, im Gegenzug verlieren wir dadurch aber etwas „Performance“, da wir ja zusätzlich zu jedem Vergleich nun noch 2 Multiplikationen brauchen.

Wir werden uns nun zuerst darum kümmern, die Heap-Eigenschaft aufrecht zu erhalten, bevor wir uns ansehen, wie wir aus einer Menge Daten einen Heap konstruieren. Dazu benötigen wir eine elementare Operation, das „Versickern“ eines Knotens.

Wenn wir einen bestimmten Knoten betrachten, dann können wir schnell feststellen, ob er lokal gesehen richtig platziert ist oder nicht. Erinnern wir uns an die Heap-Eigenschaft(en), dann wissen wir, dass die Kinder dieses einen Knotens auf jeden Fall kleiner (im Fall eines Max-Heaps, bei einem Min-Heap größer) sein müssen als der Knoten selbst. Wenn diese Eigenschaft bei diesem einen Knoten nicht erfüllt ist, dann können wir das korrigieren, in dem wir den Knoten mit dem größeren (kleineren) der beiden Kindknoten vertauschen. Nach dem Vertauschen müssen wir allerdings sicherstellen, dass die Heap-Eigenschaft im Teilbaum des ehemaligen Kindes (also der Baum, der sich NUN unterhalb des einen betrachteten Knoten befindet) noch erhalten ist. Das funktioniert nach dem selben Schema wie gerade schon angesprochen.

Auf diese Weise wandert der eine Knoten so lange am Baum herab nach unten, bis er an einer Position ist, an der er die Heap-Eigenschaft nicht stört. Deshalb spricht man in diesem Zusammenhang vom „Versickern“.

Nun wird deutlich, warum diese Implementierung generell als die „kompliziertere“ verstanden wird: Es werden einige Zeiger umgesetzt. Falsch gesetzte Zeiger führen hier natürlich zur Katastrophe.

/*
 * Elementare Funktion des Versickerns.
 * Der übergebene Knoten sollte existieren und sich im Heap befinden!
*/
void heap_heapify(struct Heap* h, struct HeapNode* node)
{
    struct HeapNode* swap_partner = node;
 
    /*
     * Wenn der Knoten ein linkes Kind hat, dann überprüfe, ob es größer (kleiner) als 
     * der aktuelle Knoten ist.
    */ 
    if (node->left != NULL)
    {
        if ((node->left->data * h->factor) > (node->data * h->factor))
        {
            swap_partner = node->left;
        }
 
        /*
         * Wenn der Knoten ein rechtes Kind hat, dann überprüfe, ob es größer (kleiner) als 
         * das bisher größte (kleinste) Element ist.
         * Der Knoten hat nur dann ein rechtes Kind, wenn er auch ein linkes hat!
        */
        if (node->right != NULL)
        {
            if ((node->right->data * h->factor) > (swap_partner->data * h->factor))
            {
                swap_partner = node->right;
            }
        }
    }
 
    /*
     * Wenn einer der Kindknoten größer (kleiner) als der aktuelle Knoten ist, 
     * dann vertausche die beiden und fahre mit dem entsprechenden Teilbaum fort.
    */
    if (swap_partner != node)
    {
        /*
         * Darauf achten, dass auch der Zeiger des Elternknotens angepasst wird!
         * Wenn es keinen Elternknoten gibt, dann ist der Knoten der root-Knoten,
         * in dem Fall muss der root Zeiger des Heaps angepasst werden!
        */
        if (node->parent != NULL)
        {
            if (node->parent->left == node)
            {
                node->parent->left = swap_partner;
            }
            else
            {
                node->parent->right = swap_partner;
            }
        }
        else
        {
            h->root = swap_partner;
        }
        /*
         * Je nach dem, mit welchem Kind getauscht wird, müssen unterschiedliche
         * Zeiger angepasst werden.
        */
        if (swap_partner == node->left)
        {
            node->left = swap_partner->left;
            swap_partner->left = node;
            struct HeapNode* temporary = node->right;
            node->right = swap_partner->right;
            swap_partner->right = temporary;
        }
        else
        {
            node->right = swap_partner->right;
            swap_partner->right = node;
            struct HeapNode* temporary = node->left;
            node->left = swap_partner->left;
            swap_partner->left = temporary;
        }
 
        /*
         * node befindet sich nun eine Ebene tiefer, also müssen
         * wir auch auf dieser Ebene überprüfen, ob die Heap-Eigenschaft
         * nicht verletzt ist und es notfalls korrigieren!
        */
        heap_heapify(h,node);
    }
}

Im folgenden Code ist hier nun gut zu sehen, dass die Datenwerte kopiert werden. Das kann bei großen Datenblöcken (hier sind es ja nur einzelne Integer) mitunter lange dauern. Abhilfe kann man natürlich durch Verwendung von Zeigern auf die Daten schaffen, aber dann müssen auch alle sonstigen Operationen entsprechend angepasst werden!

/*
 * Elementare Funktion des Versickerns. Der übergebene Index ist ab 0 gezählt.
*/
void heap_heapify(struct Heap* h, int index)
{
    // Umgeformt aus (2*(index+1) - 1) um verschiedene Indizierungsweisen auszugleichen
    int left = (2 * index) + 1;
    int right = left + 1;
    int swap_partner = index;
 
    /*
     * Wenn der Knoten ein linkes Kind hat, dann überprüfe, ob es größer (kleiner) als 
     * der aktuelle Knoten ist.
    */ 
    if (left < h->size)
    {
        if ((h->data[left] * h->factor) > (h->data[index] * h->factor))
        {
            swap_partner = left;
        }
 
 
        /*
         * Wenn der Knoten ein rechtes Kind hat, dann überprüfe, ob es größer (kleiner) als 
         * das bisher größte (kleinste) Element ist.
         * Der Knoten hat nur dann ein rechtes Kind, wenn er auch ein linkes hat!
        */
        if (right < h->size)
        {
            if ((h->data[right] * h->factor) > (h->data[swap_partner] * h->factor))
            {
                swap_partner = right;
            }
        }
    }
 
 
    /*
     * Wenn einer der Kindknoten größer (kleiner) als der aktuelle Knoten ist, 
     * dann vertausche die beiden und fahre mit dem entsprechenden Teilbaum fort.
    */
    if (swap_partner != index)
    {
        int temporary = h->data[index];
        h->data[index] = h->data[swap_partner];
        h->data[swap_partner] = temporary;
 
        heap_heapify(h,swap_partner);
    }
}

Mit Hilfe dieser elementaren Operation werden fast alle anderen Operation am Heap, wie zum Beispiel das Einfügen eines einzelnen Wertes oder das Extrahieren des Maximums (bzw. Minimums) realisiert.

In jedem Heap existiert ein „Extremwert“. Dieser befindet sich an der Spitze, also der Wurzel, des Baumes. Je nach verwendeter Heap-Eigenschaft ist dieser Wert ein Maximum, da laut der Max-Heap-Eigenschaft alle unter ihm befindlichen Knoten einen kleineren Wert haben müssen oder analog bei der Min-Heap-Eigenschaft ein Minimum. Daher ist es nicht schwer, diesen Extremwert zu finden, diese Operation kann also in konstanter Zeit durchgeführt werden.

Bei dieser Implementation müssen wir lediglich darauf achten, dass der root Knoten ja auch NULL sein kann. Das ist der Fall, wenn der Heap keine Elemente enthält.

/*
 * Gebe das Maximum (Minimum) des Heaps aus.
*/
int heap_extremum(struct Heap* h)
{
    if (h->root != NULL)
    {
        return h->root->data;
    }
    else
    {
        return 0;
    }
}

Auch bei dieser Implementierung muss überprüft werden, ob sich überhaupt ein Element im Heap befindet. Wenn dem nicht so ist, wird ein Standardwert zurückgegeben.

/*
 * Gebe das Maximum (Minimum) des Heaps aus.
*/
int heap_extremum(struct Heap* h)
{
    if (h->size != 0)
    {
        return h->data[0];
    }
    else
    {
        return 0;
    }
}

Da wir nun wissen, wo sich der Extremwert im Heap befindet, werden wir uns jetzt ansehen, wie man den Extremwert aus dem Heap extrahiert, sprich herausnimmt. Das ist wichtig, z.B. für die Implementierung einer Prioritätswarteschlange. So kann immer das Objekt mit der höchsten Priorität aus dem Heap entnommen werden.

Wenn wir den Extremwert aus dem Heap herausnehmen bedeutet das konkret, dass wir die Wurzel des Baumes entfernen und durch den „letzten“ Wert im Heap ersetzen. In der Baumdarstellung ist das der Knoten, der sich in der letzten Ebene am weitesten rechts befindet. In der Arraydarstellung ist es das letzte Element.

Wir setzen den letzten Knoten an die Wurzel des Baumes. Das Komplizierteste an dieser Operation ist das Finden des neuen „letzten Knotens“.

struct HeapNode* heap_propagate_left(struct Heap* h, struct HeapNode* n)
{
    struct HeapNode* walker = n;
    while (walker != h->root && walker == walker->parent->left)
    {
        walker = walker->parent;
    }
    if (walker != h->root)
    {
        walker = walker->parent->left;
    }
    while (walker->right != NULL)
    {
        walker = walker->right;
    }
    return walker;
}
 
 
/*
 * Extrahiere den Extremwert aus dem Heap.
*/
int heap_extract_extremum(struct Heap* h)
{
    if (h->root == NULL)
    {
        return NULL;
    }
    int extremum = h->root->data;
    if (h->root->left == NULL)
    {
        free(h->root);
        return extremum;
    }
 
    struct HeapNode* lnode = h->last_node;
    if (lnode->parent->left == lnode)
    {
        h->last_node = heap_propagate_left(h,lnode);
        lnode->parent->left = NULL;
    }
    else //if (h->last_node->parent->right == lnode)
    {
        lnode->parent->right = NULL;
        h->last_node = lnode->parent->left;
    }
 
    lnode->parent = NULL;
    lnode->left = h->root->left;
    lnode->left->parent = lnode;
    lnode->right = h->root->right;
    lnode->right->parent = lnode;
    free(h->root);
    h->root = lnode;
    heap_heapify(h,h->root);
 
    return extremum;
}

/*
 * Extrahiere den Extremwert aus dem Heap.
*/
int heap_extract_extremum(struct Heap* h)
{
    if (h->size == 0)
    {
        return NULL;
    }
    int extremum = h->data[0];
    h->size--;
    h->data[0] = h->data[h->size];
    heap_heapifiy(h, 0);
    return extremum;
}

Als nächstes betrachten wir, wie wir den Wert eines Knotens erhöhen (im Fall der Max-Heap-Eigenschaft) bzw verringern (im Fall der Min-Heap-Eigenschaft) können. Diese Operation werden wir hauptsächlich dazu verwenden, neue Knoten einzufügen.

Die Operation an sich ist einfach: Wir erhöhen/vermindern den Wert des Knotens, und anschließend vertauschen wir den Knoten so lange mit seinem aktuellen Elternknoten, bis der Elternknoten größer/kleiner als der aktuelle Knoten ist.

Viel Code für eine eigentlich so simple Aufgabe: Alles, was wir hier machen, ist ein paar Knoten zu vertauschen.

void heap_change_key(struct Heap* h, struct HeapNode* n, int val)
{
    if ((val * h->factor) <= (n->data * h->factor))
    {
        return;
    }
    n->data = val;
    struct HeapNode* walker = n;
    while (n->parent != NULL
           && ((n->data * h->factor) > (n->parent->data * h->factor)))
    {
        struct HeapNode* swap_partner = n->parent;
        struct HeapNode* temporary_left = n->left;
        struct HeapNode* temporary_right = n->right;
        if (n == n->parent->left)
        {
            n->right = n->parent->right;
            n->left = n->parent;
        }
        else
        {
            n->left = n->parent->left;
            n->right = n->parent;
        }
        if (n->parent->parent->left == n->parent)
        {
            n->parent->parent->left = n;
        }
        else
        {
            n->parent->parent->right = n;
        }
        n->parent = swap_partner->parent;
        swap_partner->left = temporary->left;
        swap_partner->right = temporary->right;
    }
}

void heap_change_key(struct Heap* h, int index, int val)
{
    if ((val * h->factor) <= (h->data[index] * h->factor))
    {
        return;
    }
    h->data[index] = val;
    int i = index;
    while (i > 0 && ((h->data[i] * h->factor) > (h->data[i/2] * h->factor)))
    {
        int temporary = h->data[i];
        h->data[i] = h->data[i/2];
        h->data[i/2] = temporary;
        i = i/2;
    }
}

Das Einfügen eines Wertes ist nun nicht mehr schwer. Wir hängen einen leeren Knoten an das „Ende“ des Heaps an und wenden dann die gerade kennengelernte Operation zum Erhöhen/Vermindern an. Das „Ende“ bezeichnet hierbei die nächste freie Stelle von links aus gesehen auf der untersten Ebene des Baumes, wenn wir von einer Baumdarstellung ausgehen. Ansonsten ist das Ende einfach hinter dem aktuell letzten Element im Array.

//TODO

void heap_insert(struct Heap* h, int val)
{
    if (h->size == HEAP_SIZE)
    {
        return;
    }
    h->data[h->size] = val - h->factor;
    h->size++;
    heap_change_key(h, h->size-1, val);
}

Der gesamte Quellcode, der in diesem Artikel verwendet wird, steht (BALD) auch zum Download verfügbar. Das schließt zum einen die Implementierung als Baum als auch die Implementierung als Array ein. Es können NICHT beide gleichzeitig verwendet werden, da es sonst zu Benennungskonflikten kommen wird ;)

Ich hoffe ihr konntet aus dem Artikel mitnehmen, was genau ein Heap ist, wozu er nützlich ist und wie er implementiert werden kann. Die hier gezeigte Implementierung hat natürlich keinen Anspruch darauf, die bestmögliche Implementierung zu sein!

Fragen jeder Art könnt ihr im Forum stellen! Wenn euch etwas unklar ist, und ihr etwas genauer (besser) erklärt haben wollt, dann schreibt einfach ;)