Heap Dwuwymiarowy: Struktura Danych i Algorytmy

Binary Heap: A Dense Array

A binary heap is a complete binary tree — every level full except possibly the last, which fills left to right — stored with no pointers at all. Because the shape is always the same predictable shape, a node's children can be computed from its index alone, so the whole tree lives in one flat array:

parent(i) = (i - 1) >> 1 left(i) = 2*i + 1 right(i) = 2*i + 2 No child pointers, no parent pointers, no allocator calls per node. The array is dense and cache-friendly, which is a large part of why heaps beat pointer-based trees in practice even though both offer O(log n) operations on paper.

parent(i) = (i - 1) >> 1
left(i)   = 2*i + 1
right(i)  = 2*i + 2

Właściwość sterty jest słabsza, niż się wydaje

Sterta gwarantuje jedynie, że każdy rodzic jest mniejszy lub równy swoim dzieciom. Nie oznacza to jednak, że jest posortowana – sterte nic nie mówi o porządku między rodzeństwem, ani między węzłem a jego wczem. Zapewnia ona jedynie, że szczyt drzewa zawiera minimum wszystkich elementów poniżej niego. Ta słabsza obietnica stanowi całą sztuczkę: jej egzekwowanie kosztuje O(log n) na zmianę zamiast O(log n) plus ponowne balansowanie struktury w pełni posortowanej.

Wstawianie: wstawianie wartości

Wstawienie dodaje nową wartość na wolnym miejscu – następne po ostatnim liście – co utrzymuje drzewo w stanie pełnym. Ta nowa gałąź wtedy przesuwa się w górę: dopóki jest mniejsza od rodzica, wymień ją z rodzicem i powtórz. Drzewo ma wysokość ⌊log₂ n⌋, więc odbywa się maksymalnie tyle swapów.

function siftUp(a, i) {
  while (i > 0) {
    const p = (i - 1) >> 1;
    if (a[p] <= a[i]) break;
    [a[p], a[i]] = [a[i], a[p]];
    i = p;
  }
}

Spadanie: wydobywanie minimum

Aby usunąć minimum, należy podnieść wartość korzenia, przenieść ostatni element tablicy do slotu korzenia, zmniejszyć tablicę o jeden element i przeprowadzić sortowanie w dół: wielokrotnie zamieniać go z mniejszym z jego dwóch dzieci, aż nie będzie ono większe niż którekolwiek z nich. Operacja ta kosztuje maksymalnie O(log n) operacji wymiany i jest to działanie wykorzystywane w algorytmie Dijkstry, A* oraz we wszystkich planerach zdarzeń dyskretnych dostępnych na tej stronie, które są wywoływane tysiące razy na sekundę.

function siftDown(a, i, n) {
  for (;;) {
    let s = i, l = 2*i+1, r = 2*i+2;
    if (l < n && a[l] < a[s]) s = l;
    if (r < n && a[r] < a[s]) s = r;
    if (s === i) break;
    [a[s], a[i]] = [a[i], a[s]];
    i = s;
  }
}

Budowanie stosu w czasie O(n) i sortowanie przez kopcowanie

Wywołanie `sift-up` n razy, aby zbudować kopiec od zera, kosztuje O(n log n). Floyd z 1964 roku robi to lepiej: zaczyna się od ostatniego węzła nie-liścia i przeprowadzany jest proces `sift-down` dla każdego węzła od dołu do góry aż do korzenia. Wydaje się, że powinno to kosztować O(n log n), ale tak naprawdę nie – większość węzłów znajduje się blisko dołu drzewa, gdzie ich wysokość, a więc i maksymalna liczba zamian, jest niewielka. Sumowanie (wysokości) pomnożone przez (liczba węzłów na danej wysokości) dla całego drzewa to szereg geometryczny, który zbiega się, dając O(n) w sumie. Powtarzalne zamiany korzenia z ostatnim elementem i przeprowadzanie procesu `sift-down` dla malejącego kopca przekształca to w sortowanie przez kopcowanie: O(n log n), w miejscu, algorytm o gwarantowanym najgorszym przypadku czasie działania – bez dodatkowej pamięci – choć nie jest stabilny, ponieważ elementy o równej wartości mogą się ze sobą przeciąć podczas zamian.

Stosowe kolejki i gdzie stosy rzeczywiście występują

Binarny stos jest przypadkiem d = 2 ogólnego stosu d-owego: każdy węzeł ma d potomków zamiast 2. Większa wartość d zmniejsza wysokość drzewa (mniej poziomów przesunięć w dół) kosztem porównywania większej liczby dzieci na każdym poziomie, aby znaleźć najmniejsze — stosy 4-owe są popularnym kompromisem dla algorytmów inspirowanych Dijkstra, gdzie wywołania zmniejszające klucz znacznie przewyższają wywołania extract-min. Ponadto stosy służą do obsługi zbioru otwartego w Dijkście i A*, kolejki gotowej w symulatorach zdarzeń dyskretnych i sieci oraz łączenia k-drogowego posortowanych przebiegów, a także klasycznemu trikowi dwóch stosów do utrzymywania bieżącej mediany: stos maksimum dla dolnej połowy danych i stos minimum dla górnej połowy, utrzymywane w od siebie na jeden element.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Binary Heap i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.