Informatyka MIMUW

Ponieważ z warunku kopca wynika, że w każdym drzewie wchodzącym w skład kolejki element najmniejszy znajduje się w korzeniu, operacja FindMin wymaga jednokrotnego przejścia listy drzew. Jej koszt to $O(\lg n)$ dla $n$-elementowej kolejki.

Najważniejszą operacją na kolejce dwumianowej, za pomocą której definiuje się większość pozostałych, jest Meld (łączenie kolejek).Jej działanie przypomina mechanizm dodawania liczb binarnych, przy czym sumowaniu jedynek na pozycji $i$ w dodawanych liczbach odpowiada łączenie dwóch drzew dwumianowych stopnia $i$ (zobacz lemat 1(d)): korzeń z mniejszym kluczem (w celu zachowania warunku kopca) zostaje korzeniem wynikowego drzewa $B_{i+1}$ ('przeniesienia'), a drugi korzeń zostaje jego skrajnie prawym synem. Łączenie dwóch kolejek polega na przejściu obydwu list drzew i złączeniu drzew jednakowych stopni. Jego koszt jest proporcjonalny do sumy długości list.

Operacja Insert (wstawienie węzła) stanowi w zasadzie szczególny przypadek Meld (łączenie z kolejką jednoelementową).Operacja DelMin(H) polega na znalezieniu i usunięciu z listy H drzewa z najmniejszym kluczem, odcięciu jego korzenia (ten klucz jest wynikiem całej operacji) i połączeniu listy jego synów (stanowiącej poprawną kolejkę dwumianową) z H. Łączny koszt to $O(\lg n)$ dla $n$-elementowej kolejki.Operację DecreaseKey wykonuje się podobnie jak poprawianie kopca binarnego przy wstawianiu elementu: zmniejszony klucz wędruje w górę swojego drzewa dwumianowego, zamieniając się miejscami z ojcem dopóty, dopóki nie zostanie odtworzony warunek kopca. W myśl lematu 1(b) maksymalna wysokość drzewa w $n$-elementowej kolejce to $O(\lg n)$, więc koszt takiej operacji jest logarytmiczny.Operacja Delete sprowadza się do przesunięcia klucza, który mamy usunąć, do korzenia (jak w DecreaseKey), a potem usunięcia tego korzenia (jak w DelMin).