Kopiec dwumianowy

Ten artykuł od 2014-06 zawiera treści, przy których brakuje odnośników do źródeł. Należy dodać przypisy do treści niemających odnośników do źródeł. Dodanie listy źródeł bibliograficznych jest problematyczne, ponieważ nie wiadomo, które treści one uźródławiają. Sprawdź w źródłach: Encyklopedia PWN • Google Books • Google Scholar • Federacja Bibliotek Cyfrowych • BazHum • BazTech • RCIN • Internet Archive (texts / inlibrary) Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Kopiec dwumianowy – struktura danych umożliwiająca łatwe wykonywanie zwykłych operacji kopcowych (insert, findmin, deletemin) oraz operacji łączenia kopców (meld)^[1]. 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 ${\displaystyle k}$ składa się z korzenia oraz jego dzieci, którymi są drzewa dwumianowe rzędów ${\displaystyle k-1,k-2,\dots ,1,0}$ (dokładnie w tej kolejności).

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

Drzewo dwumianowe rzędu ${\displaystyle k}$ może być łatwo zbudowane z dwóch drzew rzędu ${\displaystyle 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 ${\displaystyle {\binom {n}{d}},}$ która mówi o liczbie węzłów na poziomie d drzewa dwumianowego rzędu ${\displaystyle 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 ${\displaystyle n}$ elementów składa się z co najwyżej ${\displaystyle \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 ${\displaystyle n.}$ Na przykład 13 to 1101 w systemie dwójkowym, ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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).

Przypisy

Bibliografia

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