Kopiec (binarny)

30.11.2009 - Michał Karpiński
Trudność

Czym jest kopiec ?

Zanim odpowiem na to pytanie najpierw powinieneś poznać kilka nowych pojęć związanych z kopcami:

  • węzeł - każdy element kopca

  • rodzic - węzeł stojący o jeden stopień wyżej w hierarchii drzewa. Połączony krawędzią z danym węzłem.

  • potomek - węzeł stojący o jeden stopień niżej w hierarchii drzewa. Połączony krawędzią z danym węzłem.

  • korzeń - pierwszy węzeł kopca. Nie posiada rodzica

  • liść - węzeł nie posiadający potomka

  • wysokość węzła - liczba krawędzi o najdłuższej ścieżce prowadzącej od tego węzła do liścia

  • wysokość kopca - wysokość korzenia

Przedstawię teraz najkrótszą znaną mi definicję kopca: „kopiec jest to drzewiasta struktura danych, która spełnia własność kopca”. Oznacza to, że wartości potomków węzła są w stałej relacji z wartością rodzica. Istnieją bowiem dwie ważne odmiany kopców: kopce typu max i kopce typu min. W obydwu przypadkach wartości w węzłach spełniają własność kopca zależną od typu kopca:

  • kopce typu max – wartość każdego węzła jest większa od wartości jego potomka

  • kopce typu min – wartość każdego węzła jest mniejsza od wartości jego potomka

Oczywiście własności te zachodzą dla wszystkich węzłów poza korzeniem (ponieważ korzeń nie ma rodzica).

Poniżej znajduje się przykład reprezentacji kopca typu max w postaci drzewa binarnego oraz tablicy. Zauważ, że ponumerowaliśmy wszystkie węzły od lewej do prawej tak, żeby liczba nad węzłem w kopcu odpowiadała indeksowi w tablicy. Linie łączące elementy w tablicy przedstawiają relację rodzic-potomek.

Patrząc na rysunek nie trudno się domyśleć jak wyglądają procedury znajdowania indeksu rodzica oraz lewego i prawego potomka:

  • PARENT( i ): return floor(i/2); // floor to część całkowita liczby, tzw. "zaokrąglenie w dół"
  • LEFT( i ): return 2i;
  • RIGHT( i ): return 2i+1;

Proste ćwiczenie

Czy ciąg [23,17,14,6,13,10,1,5,4,12] jest kopcem typu max?

Aby rozwiązać to zadanie należy znaleźć wszystkie krawędzie łączące węzły z ich potomkami sprawdzając przy okazji czy relacja między rodzicem a potomkiem spełnia własność kopca typu max.

Okazuje się, że podany ciąg jest kopcem typu max. Ilustracja w postaci drzewa:

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com