Kopiec dwumianowy

Kopiec dwumianowy – struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld). Jest to lista uporządkowanych (względem rzędu) drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym.

Drzewo dwumianowe

Drzewo dwumianowe (ang. binomial tree) B_k jest drzewem poszukiwań zdefiniowanym rekurencyjnie w sposób następujący:

• drzewo dwumianowe rzędu 0 składa się z jednego węzła (korzenia);
• drzewo dwumianowe rzędu $k$ składa się z korzenia oraz jego dzieci, którymi są drzewa dwumianowe rzędów $k-1,k-2,\dots ,1,0$ (dokładnie w tej kolejności).

Drzewa dwumianowe rzędu od 0 do 3: Każde drzewo dwumianowe zawiera wszystkie drzewa niższych rzędów. Na przykład drzewo dwumianowe rzędu 3 jest złożone z korzenia i drzew rzędu 2, 1 oraz 0 (zaznaczonych odpowiednio niebieskim, zielonym i czerwonym kolorem).

Drzewo dwumianowe rzędu $k$ ma $2^{k}$ węzłów i wysokość $k.$

Drzewo dwumianowe rzędu $k$ może być łatwo zbudowane z dwóch drzew rzędu $k-1,$ przez dołączenie jednego z nich jako najbardziej lewego syna do korzenia drugiego. Ta cecha jest kluczowa dla operacji łączenia, która jest główną przewagą kopców dwumianowych nad innymi kopcami.

Nazwa pochodzi od zależności ${\binom {n}{d}},$ która mówi o liczbie węzłów na poziomie d drzewa dwumianowego rzędu $n.$

Struktura kopca dwumianowego

Kopiec dwumianowy implementuje się jako zbiór drzew dwumianowych zachowujących własności kopca dwumianowego:

• Każde drzewo dwumianowe zachowuje własność kopca: wartość węzła jest większa lub równa niż wartość jego rodzica.
• W kopcu może znajdować się co najwyżej jedno drzewo z każdego rzędu.

Pierwsza własność gwarantuje, że każdy korzeń drzewa dwumianowego zawiera najmniejszą wartość w drzewie, co stosuje się do całego kopca.

Dzięki drugiej własności wiemy, że kopiec dwumianowy zawierający $n$ elementów składa się z co najwyżej $\lg n+1$ drzew dwumianowych. Istotnie, liczba i rzędy tych drzew są jednoznacznie wyznaczone przez liczbę elementów w kopcu: każde drzewo odpowiada jedynce w reprezentacji dwójkowej liczby $n.$ Na przykład 13 to 1101 w systemie dwójkowym, $2^{3}+2^{2}+2^{0},$ a więc kopiec dwumianowy z 13 elementami będzie się składał z 3 drzew o rzędach 3, 2 i 0 (patrz rysunek niżej).

Przykładowy kopiec dwumianowy o 13 rozróżnialnych elementach.
Kopiec składa się z 3 drzew dwumianowych rzędów 0, 2 i 3.

W kopcu dwumianowym, operację findmin (znalezienia najmniejszego elementu) wykonuje się poprzez sprawdzenie wszystkich korzeni drzew dwumianowych. Wymaga to $O(\log n)$ operacji.

Operacje insert wykonuje się w sposób analogiczny do dodawania liczby 1 w reprezentacji binarnej.

• Tworzymy drzewo dwumianowe o wielkości 1 zawierające dodawany element.
• Jeśli w kopcu nie ma drzewa o wielkości 1, dodajemy je na początku listy drzew i kończymy.
• Jeśli w kopcu jest drzewo o wielkości 1, dokonujemy złączenia obu drzew (tej samej wielkości). Wybieramy jedno z tych drzew (o mniejszym korzeniu), i dodajemy drugie drzewo jako jego potomka. Tworzymy w ten sposób drzewo dwumianowe o wielkości 2.
• Podobnie, sprawdzamy czy drzewo o tej samej wielkości istnieje już w kopcu, jeśli nie, dodajemy i kończymy, jeśli tak dokonujemy złączenia w analogiczny sposób, przy czym drugie drzewo zostaje dodane jako najbardziej lewy potomek, tak aby drzewo miało strukturę drzewa dwumianowego.
• Powtarzamy analogicznie te kroki, aż skończymy (ostatecznie dojdziemy do ostatniego drzewa, i wtedy kopiec będzie chwilowo pusty).

Procedura ta jest podobna do dodawania binarnego z przeniesieniem. Koszt obliczeniowy to $O(\log n)$ operacji.

Operację meld (łączenia dwóch kopców), wykonujemy w identyczny sposób jak dodawanie dwóch liczb binarnych. Zaczynamy łączenie od najmniejszych drzew (najmniej znaczące bity w liczbie binarnej), i pamiętamy w razie potrzeby przeniesienie.

W rzeczywistości operację insert można rozumieć jako operację meld na oryginalnym kopcu i kopcu jednoelementowym (w jednym drzewem o wielkości 1).

W przypadku operacji deletemin (usunięcie najmniejszego elementu), najpierw wyszukujemy element (tak jak w findmin), usuwamy korzeń znalezionego drzewa wielomianowego i dokonujemy operacji meld z kopcem dwumianowym który powstałby z potomków tego drzewa (potomkowie ci to zbiór drzew dwumianowych, w których drzewa się nie powtarzają z konstrukcji, mają również właściwość kopca, a więc jest to też kopiec dwumianowy).

Bibliografia

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.