Kopiec dwumianowy


Kopiec dwumianowy w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania

Kopiec dwumianowystruktura 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.

Spis treści

Drzewo dwumianowe | 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 {\displaystyle k} składa się z korzenia oraz jego dzieci, którymi są drzewa dwumianowe rzędów k 1 , k 2 , , 1 , 0 {\displaystyle 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 {\displaystyle k} ma 2 k {\displaystyle 2^{k}} węzłów i wysokość k . {\displaystyle k.}

Drzewo dwumianowe rzędu k {\displaystyle k} może być łatwo zbudowane z dwóch drzew rzędu k 1 , {\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 ( n d ) , {\displaystyle {\binom {n}{d}},} która mówi o liczbie węzłów na poziomie d drzewa dwumianowego rzędu n . {\displaystyle n.}

Struktura kopca dwumianowego | 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 {\displaystyle n} elementów składa się z co najwyżej lg n + 1 {\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 n . {\displaystyle n.} Na przykład 13 to 1101 w systemie dwójkowym, 2 3 + 2 2 + 2 0 , {\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 O ( log n ) {\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 O ( log n ) {\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 | edytuj kod

  1. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein ↓, s. 454.

Bibliografia | edytuj kod

  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein: Wprowadzenie do algorytmów. WNT, 2007.
Na podstawie artykułu: "Kopiec dwumianowy" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy