WikiDer > Haufen

Heap
Abbildung 1: Das hea-Array [100, 19, 36, 17, 3, 25, 1, 2, 7] wird als Baum angezeigt.

EIN Haufen ist eine Zusammenfassung Datenstruktur in dem Informatik, nicht zu verwechseln mit einem sogenannten Haufen Speicher. Datenelemente können auf einem Heap gespeichert, aber auch daraus entfernt werden. Jedem der Elemente ist ein Schlüssel zugeordnet, der die Priorität des Elements bestimmt. In vielen Fällen können die Elemente selbst als Schlüssel verwendet werden.

Ein Heap ist eine Array-Datenstruktur mit a Binärbaum repräsentiert. Eine Anordnung ein ist ein Haufen, wenn es die erfüllt Haufenzustand: wenn B ein Kind von ein ist, dann Schlüssel (ein) ≥ Taste(B).

Betrieb

Element hinzufügen

Beginnt mit einem Array ein mit Größe Nein. Das zu platzierende Element wird platziert N 1 stellen. An dieser Stelle sind die Anforderungen nicht unbedingt erfüllt Haufenzustand (Das Element kann größer sein als sein Elternteil.) Um die Heap-Bedingung wieder zu erfüllen, werden die folgenden Schritte wiederholt, bis das Element an Ort und Stelle ist, dh kleiner als sein Elternteil. Wenn das hinzugefügte Element das größte des gesamten Heaps ist, wird es schließlich in der Wurzel platziert.

  1. Ist der Schlüssel des neuen Elements größer als sein Elternteil?
    1. Wenn ja: Übergeordnete und neue Elementorte wechseln
    2. Falls nicht: Die Heap-Bedingung ist jetzt wieder erfüllt und das Element ist vorhanden.

Codebeispiel (C )

Vorlage<ModellnameT>LeereHeapSort<T>::element_add(Vektor<T>&v,TElement){//Anmerkung: der Vektor verwendet die Indizes [0..N-1, der Heap [1..N]v.push_back(Element);intich=v.Größe();//Index des neu hinzugefügten Elementswährend(ich>1&&v[ich-1]>v[ich/2-1]){//Elternteil hat Index i/2Tauschen(v[ich-1],v[ich/2-1]);ich=ich/2;//das Element befindet sich jetzt an der Stelle seines Elternteils, wir beginnen wieder an dieser Stelle}}

Anwendungen