DAA - Binary Heap

Istnieje kilka typów stert, jednak w tym rozdziale omówimy stertę binarną. ZAbinary heapto struktura danych, która wygląda podobnie do pełnego drzewa binarnego. Struktura danych sterty jest zgodna z właściwościami porządkowania omówionymi poniżej. Ogólnie sterta jest reprezentowana przez tablicę. W tym rozdziale przedstawiamy stertę wgH.

Ponieważ elementy sterty są przechowywane w tablicy, biorąc pod uwagę indeks początkowy jako 1, pozycja węzła macierzystego i^th element można znaleźć pod adresem ⌊ i/2 ⌋. Lewe dziecko i prawe dzieckoi^th węzeł jest na pozycji 2i i 2i + 1.

Stertę binarną można dalej sklasyfikować jako plik max-heap lub a min-heap na podstawie właściwości zamawiającego.

Max-Heap

W tej stercie wartość klucza węzła jest większa lub równa wartości klucza najwyższego elementu potomnego.

W związku z tym, H[Parent(i)] ≥ H[i]

Min-Heap

W mean-heap wartość klucza węzła jest mniejsza lub równa wartości klucza najniższego elementu podrzędnego.

W związku z tym, H[Parent(i)] ≤ H[i]

W tym kontekście podstawowe operacje są pokazane poniżej w odniesieniu do Max-Heap. Wstawianie i usuwanie elementów ze stert i ze stert wymaga zmiany układu elementów. W związku z tym,Heapify funkcja musi zostać wywołana.

Reprezentacja tablicy

Kompletne drzewo binarne może być reprezentowane przez tablicę, przechowującą jego elementy przy użyciu przechodzenia do kolejności poziomów.

Rozważmy stertę (jak pokazano poniżej), która będzie reprezentowana przez tablicę H.

Biorąc pod uwagę indeks początkowy jako 0przy użyciu przechodzenia w kolejności poziomów elementy są przechowywane w tablicy w następujący sposób.

Index	0	1	2	3	4	5	6	7	8	...
elements	70	30	50	12	20	35	25	4	8	...

W tym kontekście operacje na stercie są reprezentowane w odniesieniu do Max-Heap.

Aby znaleźć indeks rodzica elementu w index i, następujący algorytm Parent (numbers[], i) jest używany.

Algorithm: Parent (numbers[], i) 
if i == 1 
   return NULL 
else 
   [i / 2]

Indeks lewego dziecka elementu w index i można znaleźć za pomocą następującego algorytmu, Left-Child (numbers[], i).

Algorithm: Left-Child (numbers[], i) 
If 2 * i ≤ heapsize 
   return [2 * i] 
else 
   return NULL

Indeks prawego dziecka elementu o indeksie i można znaleźć za pomocą następującego algorytmu, Right-Child(numbers[], i).

Algorithm: Right-Child (numbers[], i) 
if 2 * i < heapsize 
   return [2 * i + 1] 
else 
   return NULL