Motywacja

Sortowanie przez kopcowanie wykorzystuje kopiec binarny, aby wielokrotnie znajdować największy pozostały element w czasie O(log n), zapewniając niezawodne sortowanie w czasie O(n log n).

Dlaczego warto poznać sortowanie przez kopcowanie?

• Gwarantowane O(n log n): w przeciwieństwie do szybkiego sortowania, nie ma najgorszego przypadku O(n²).
• W miejscu: sortuje w oryginalnej tablicy i wymaga tylko O(1) dodatkowej pamięci, w przeciwieństwie do sortowania przez scalanie.
• Intuicja dotycząca kopca: utrwala wiedzę o tym, jak kopiec jest przechowywany w tablicy i jak operacja przesiewania w dół utrzymuje jego poprawność.

Jeśli znasz już kurs o kopcach z tej serii, sortowanie przez kopcowanie pokazuje, jak wykorzystać tę strukturę danych jako algorytm sortowania.