Jak to działa?

Kopiec binarny znajduje się w zwykłej tablicy. Dla węzła o indeksie i (liczonym od 0) jego dzieci znajdują się pod indeksami 2*i + 1 i 2*i + 2. To indeksowanie jest całym trikiem, który pozwala umieścić drzewo w tablicy.

Proces krok po kroku:

1. Zbuduj kopiec maksymalny: przestaw elementy tablicy tak, aby każdy rodzic był większy lub równy swoim dzieciom. Największa wartość znajdzie się pod indeksem 0.
2. Wyodrębnij maksimum: zamień korzeń (największy element) z ostatnim elementem kopca, a następnie zmniejsz kopiec o jeden element, aby największy element znalazł się na końcu, na swojej docelowej pozycji w posortowanej tablicy.
3. Napraw kopiec, przesiewając w dół: nowy korzeń może być na niewłaściwym miejscu, więc przesiej go w dół (zamień go z większym dzieckiem i powtarzaj), aż własność kopca zostanie przywrócona.
4. Powtarzaj, aż kopiec będzie pusty. Tablica jest teraz posortowana rosnąco.

Przykład dla [4, 10, 3, 5, 1]:

• Zbuduj kopiec maksymalny: [10, 5, 3, 4, 1].
• Zamień korzeń 10 z ostatnim elementem i przesiej go w dół, a następnie powtórz dla 5, 4, 3.
• Wynik: [1, 3, 4, 5, 10].