Datenstrukturen: Heap

"Ein Heap ist eine lineare Datenstruktur, die Elemente nach Priorität organisiert, wobei das größte Element immer am Anfang steht. Dargestellt als vollständiger binärer Baum, gewährleistet ein Heap, dass jeder Elternknoten eine höhere Priorität als seine Kinder hat. Operationen wie Selektion, Einfügen und Entfernen haben eine Komplexität von O(log n), da sie das Hoch- oder Runterfahren des Baums erfordern, um die Ordnung aufrechtzuerhalten. Die Änderung der Priorität hat auch eine Komplexität von O(log n). Der "Hochfahren"-Algorithmus verschiebt Elemente nach oben im Baum, wenn ihre Priorität höher ist als die ihrer Eltern. Der "Runterfahren"-Algorithmus verschiebt Elemente nach unten, wenn ihre Priorität niedriger ist als die ihrer Kinder. Das Einfügen eines neuen Elements erfolgt, indem es am Ende hinzugefügt und dann im Baum hochgefahren wird, um die Ordnung aufrechtzuerhalten. Das Entfernen des Elements mit der höchsten Priorität erfolgt, indem es durch das letzte Element ersetzt und dann im Baum runtergefahren wird, um die Ordnung aufrechtzuerhalten. Ein Heap kann durch Ordnen einer Liste (O(n log n)) oder durch das Runterfahren der internen Knoten des Baums ab der Mitte der Liste (O(n)) konstruiert werden."