Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Kopiec
Kopiec jest drzewem binarnym, które musi spełnić następujący warunek, tzw. warunek kopca:
Węzeł nadrzędny jest większy lub równy węzłom potomnym
(w porządku malejącym relacja jest odwrotna - mniejszylub równy)
Własności kopca:
korzeń zawsze jest największym (w porządku malejącym najmniejszym) elementem z całego drzewa binarnego
uporządkowanie- wartość każdego wierzchołka (rodzica) jest większa niż wartości jego potomków.
kształt- synowie znajdują się na jednym lub więcej poziomach, a te na najniższym poziomie (liście) są przesunięte jak najbardziej w lewo. Wynika z tego, że jeżeli drzewo zawiera n wierzchołków, to żaden z nich nie jest bardziej oddalony od korzenia niż o (log n) węzłów.
Własności te są warunkami na tyle silnymi, aby umożliwić szybkie odnalezienie elementu największego lub najmniejszego w zbiorze,a jednocześnie umożliwiają szybką reorganizację struktury kopca po dodaniu lub usunięciu z niego elementu.
