Kopiec binarny
Z Wikipedii
Kopiec binarny (czasem używa się też określenia sterta) (ang. binary heap) - kopiec stworzony jako drzewo binarne.
Kopiec binarny musi być kopcem zupełnym, czyli
- liście występują na ostatnim i ewentualnie przedostatnim poziomie w drzewie (gdy ostatni poziom nie jest całkowicie wypełniony) ,
- liście na ostatnim poziomie są spójnie ułożone od strony lewej do prawej.
Spis treści |
[edytuj] Przechowywanie w pamięci
Kopiec binarny bardzo łatwo przechowywać w pamięci. Zazwyczaj zapisuje się go w tablicy. Zauważmy, że każdy kolejny poziom kopca i zawiera 2i wierzchołków, z wyjątkiem poziomu ostatniego n, który może mieć od 1 do 2n wierzchołków.
Na rysunku kursywą zapisano indeksy w tablicy.
Korzeń kopca binarnego znajduje się w tablicy pod indeksem 1, jego dzieci są pod indeksami 2 i 3. Dzieci elementu nr 2 mają indeksy 4 i 5, a elementu 3 – 6 i 7. W ten sposób powyższy kopiec można przedstawić jako następującą tablicę:
| Indeks | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| Klucz | 20 | 16 | 8 | 10 | 15 | 2 | 5 | 7 | 6 | 3 |
Ogólnie:
- dzieci wierzchołka o indeksie i mają indeksy:
-
- 2i - dziecko lewe
- 2i+1 - dziecko prawe
- rodzic wierzchołka o indeksie i>1 ma indeks równy:
-
- operację tę można wykonać przesunięciem arytmetycznym w prawo - bardzo szybką operacją dostępną na praktycznie każdym mikroprocesorze
[edytuj] Dodawanie nowych wierzchołków
Załóżmy, że kopiec składa się z n elementów, zaś elementy uporządkowane są od największych (warunek kopca brzmi więc: każdy element jest większy od swoich dzieci). Dodawany wierzchołek ma klucz równy k:
- wstaw wierzchołek na pozycję n+1
- zamieniaj pozycjami z rodzicem (przepychaj w górę) aż do przywrócenia warunku kopca (czyli tak długo, aż klucz rodzica jest większy niż k, lub element dotrze na pozycję 1)
[edytuj] Usuwanie wierzchołka ze szczytu kopca
- usuń wierzchołek ze szczytu kopca
- przestaw ostatni wierzchołek z pozycji n+1 na szczyt kopca; niech k oznacza jego klucz
- spychaj przestawiony wierzchołek w dół, zamieniając pozycjami z większym z dzieci, aż do przywrócenia warunku kopca (czyli aż dzieci będą mniejsze od k lub element dotrze na spód kopca)
Zarówno wstawianie jak i usuwanie obiektów ze szczytu kopca ma złożoność O(logn).
