1.8 Verbesserte Implementation

Anstatt den Heap durch nacheinander Einfügen der Elemente aufzubauen, was bei n Elementen O(n log n) dauert, kann man durch „Setzen“ der Hälfte der Element einen Heapaufbau in O(n) gewährleisten.

1. Setze m = n div 2

2. generiere Blätter A[m+1], ..., A[n]

3. Für i = m, m-1, …, 1:
Füge A[i] als (vorläufigen) Vater von A[2i] und A[2i+1] ein
Lasse A[i] an die richtige Position sinken

zurück Inhalt vor