Kopiec dwumianowy

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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 zbiór drzew dwumianowych, które pamiętają elementy z uporządkowanego uniwersum w porządku kopcowym.

Drzewo dwumianowe[edytuj | edytuj kod]

Drzewo dwumianowe (ang. binomial tree) Bk 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, ..., 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 2k 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.

Struktura kopca dwumianowego[edytuj | edytuj kod]

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
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 potomek. 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 binomialnego.
  • 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 jedno elementowym (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 (potomkowi 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[edytuj | edytuj kod]

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