Algorytm łączenia dwóch maks. Stert?

Question

Czy istnieje wydajny algorytm scalania 2 maks. Stert, które są przechowywane w postaci tablic?

Answer 1

To zależy od rodzaju sterty.

Jeśli jest to standardowy stos, w którym każdy węzeł ma maksymalnie dwoje dzieci, a który wypełnia się, że liście znajdują się w maksymalnie dwóch różnych rzędach, nie można uzyskać lepszego niż O (n) dla scalenia.

Po prostu połącz te dwie tablice i utwórz z nich nową stertę, która zajmuje O (n).

Aby uzyskać lepszą wydajność łączenia, można użyć innego wariantu sterty, takiego jak Fibonacci-Heap, który można scalić w O (1) zamortyzowany.

Update: Należy zauważyć, że nie jest gorsza wstawić wszystkie elementy pierwszego sterty od jednego do drugiego hałdy lub odwrotnie od insercji wykonuje O (log (n)). Wraz ze stanów komentarz, nie wydaje się wiedzieć, jak kupa jest optymalnie zbudowany na początku (znowu dla standardowego kopiec binarny)

1. Utwórz tablicę i umieścić w elementach obu stosach w jakiś arbitralny zamówienie
2. rozpoczyna się teraz od najniższego poziomu. Najniższy poziom zawiera trywialne maksymalne stosy wielkości 1, więc ten poziom jest wykonywany
3. przesuń poziom wyżej. Gdy zostanie naruszony warunek sterty jednego z "stosów podrzędnych", zamień katalog główny "podobszaru" na większe dziecko. Następnie poziom 2 zostaje zakończony
4. przejście do poziomu 3. Po naruszeniu warunków sterty, należy postępować jak poprzednio. Zamień go na większe dziecko i przetwarzaj rekurencyjnie, aż wszystko się zgadza aż do poziomu 3
5. ...
6. po osiągnięciu góry, utworzyłeś nową stertę w O (n).

Pomijam tutaj dowód, ale możesz to wyjaśnić, ponieważ wykonałeś większość sterty na najniższych poziomach, gdzie nie trzeba było wymieniać dużej ilości zawartości, aby przywrócić stan stosu. Operowałeś na znacznie mniejszych "sub stertach", co jest dużo lepsze niż to, co zrobiłbyś, gdybyś wstawił każdy element do jednego z stert => wtedy będziesz operował za każdym razem na całej kupie, która zajmuje O (n) za każdym razem .

Aktualizacja 2: Dwumianowa sterty umożliwia łączenie w O (log (n)) i będzie zgodne z wymaganiami O (log (n)^2).

Answer 2

Dwa binarne stosy o rozmiarach n i k można łączyć w porównania O (log n * log k). Zobacz

Jörg-R. Sack and Thomas Strothotte, An algorithm for merging heaps, Acta Informatica 22 (1985), 172-186.

Answer 3

myślę co szukasz w tym przypadku jest kopiec dwumianowy.

Dwumianowa sterty to kolekcja drzew dwumianowych, należąca do rodziny stert scalonych. Najgorszy czas działania unii (scalenia) na 2 + dwumianowych hałdach z n całkowitymi przedmiotami w hałdach wynosi O (lg n).

Aby uzyskać więcej informacji, zobacz stronę http://en.wikipedia.org/wiki/Binomial_heap.