Kopiec Minimalny

Cel

Kopiec Minimalny to takie drzewo binarne w którym rodzic jest mniejszy od każdego elementu poniżej. Ponadto w kopcu nigdy nie wystąpią "dziury" jak może się zdarzyć w przypadki zwykłego drzewa. W tym artykule zostanie przedstawione jak napisać własną implementację kopca o listę.

Definicja

Kopiec Minimalny to drzewo binarne w którym:

• rodzic jest mniejszy od jego potomków
• pomiędzy elementami w kolejnych warstwach nie ma przerw, a wszystkie prócz ostatniej muszą być zapełnione

Oto przykładowy kopiec oraz dwa przykłady, które nie są kopcami:

Poprawny kopiec

Niepoprawny kopiec #1

Niepoprawny kopiec #2

W pierwszym niepoprawnym kopcu wartość 5 jest większa od 1, a to przeczy relacji, że rodzic jest zawsze mniejszy od potomka. Z kolei w drugim błędnym przykładzie pomiędzy elementem 6 i 8 znajduje się w rzędzie przerwa. Wartość 8 musi być nie prawym, a lewym potomkiem w takim przypadku.

Kopiec bardzo optymalnie wykorzystuje pamięć, ponieważ można go zapisać jako tablicę kolejnych elementów. Nie wymaga również przechowywania informacji o powiązanych elementach, ponieważ w celu przechodzenia indeksy potomków oraz rodzica można obliczyć z następujących wzorów:

W powyższych wzorach i oznacza numer elementu dla którego chcemy znaleźć jego rodzica lub potomka. Symbol "//" oznacza dzielenie całkowite.

Przykład

Kopiec zapisany w tablicy jako [0, 1, 4, 7, 5, 8] graficznie można przedstawić następująco:

Poprawny kopiec

Przyjmując, że elementy tablicy są indeksowane od 0 wiemy, że element "4" jest trzecim elementem w tablicy, więc i = 2. Jego rodzic ma indeks (i - 1) // 2 = 0, a więc rodzicem jest 0. Jego lewy potomek to 2·i + 1 = 5 i jest to 8. Z kolei prawy potomek miałby indeks 6, ale taki element nie istnieje. Podczas implementacji należy pamiętać, aby przed pobraniem elementu sprawdzić czy na pewno indeks znajduje się w granicach tablicy.

Złożoność

Kopiec jest strukturą danych w której następujące operacje mają podane złożoności:

Dodatkowo należy pamiętać, że złożoność pamięciowa jest liniowa i wynosi O(n).

Implementacja

Podstawa

Przed przystąpieniem do napisania funkcji operacji dodawania i usuwania należy napisać odpowiednie funkcje inicjalizujące oraz dać możliwość pobierania indeksów rodzica / potomków.

1.   List<int> dane;
3.   public KopiecMinimum() {
4.     dane = new List<int>();
5.   }
7.   int Rodzic(int i) {
8.     return (i - 1) / 2;
9.   }
11.   int Lewy(int i) {
12.     return 2 * i + 1;
13.   }
15.   int Prawy(int i) {
16.     return 2 * i + 2;
17.   }

Dodawanie

W celu dodania elementu umieszczamy go na samym końcu, a następnie sprawdzamy czy jest większy od rodzica. Jeśli nie jest to należy zamienić te dwa elementami miejscami, a następnie powtórzyć sprawdzenie warunku dla wstawianego elementu na nowej pozycji. To pomaga zachować relację pomiędzy elementami kopca.

1. public void Dodaj(int x) {
2.   int i = dane.Count;
3.   dane.Add(x);
4.   while (i != 0 && dane[Rodzic(i)] > dane[i]) {
5.     Zamien(ref dane, i, Rodzic(i));
6.     i = Rodzic(i);
7.   }
8. }

Algorytm dodaje element na końcu, a następnie powtarza zamianę elementu z jego rodzicem, aż relacja będzie poprawna, albo element stanie się korzeniem.

Usuwanie

Pobranie minimalnego elementu z kopca jest to operacja O(1), ponieważ wystarczy pobrać pierwszy element w tablicy. Jednak usunięcie tego elementu powoduje usunięcie korzenia, więc kopiec będzie trzeba potem naprawić.

1. public bool Minimum(out int wynik) {
2.   if (CzyPusty) {
3.     wynik = 0;
4.     return false;
5.   }
6.   wynik = dane[0];
7.   if (dane.Count == 1) {
8.     dane.Clear();
9.   } else {
10.     dane[0] = dane[dane.Count - 1];
11.     dane.RemoveAt(dane.Count - 1);
12.   }
13.   Napraw();
14.   return true;
15. }

Jeśli tablica nie zawiera jakichkolwiek elementów to po prostu wychodzimy z funkcji zwracając informację, że element nie został pobrany. Jeśli tablica składa się tylko z jednego elementu to wystarczy ją wyczyścić. W przeciwnym razie przesuwamy ostatni element jako pierwsze, a następnie musimy naprawić kopiec. Służy do tego funkcja Napraw() przedstawiona poniżej:

1. void Napraw(int i = 0) {
2.   int lewy = Lewy(i);
3.   int prawy = Prawy(i);
4.   int imin = i;
5.   if (lewy < dane.Count && dane[lewy] < dane[imin]) {
6.     imin = lewy;
7.   }
8.   if (prawy < dane.Count && dane[prawy] < dane[imin]) {
9.     imin = prawy;
10.   }
11.   if (imin != i) {
12.     Zamien(ref dane, i, imin);
13.     Napraw(imin);
14.   }
15. }

Funkcja napraw ma za zadanie odpowiedni przesunąć element pod indeksem i tak, aby znalazł się w odpowiednim miejscu kopca. Algorytm zakłada, że po stronie lewego jak i prawego potomka znajduje się kopiec. Jest to taka sytuacja jak podczas usuwania elementu, a potem naprawiania kopca.

Testowanie funkcji

W celu przetestowania kodu można skorzystać z poniższego fragmentu programu:

1. static void Main(string[] args) {
2.   KopiecMinimum kopiec = new KopiecMinimum();
3.   int x;
4.   Console.Write(" Wrzucamy: ");
5.   for (int i = 0; i < 10; i++) {
6.     x = (i * 17) % 10;
7.     kopiec.Dodaj(x);
8.     Console.Write("{0} ", x);
9.   }
11.   Console.Write("\nZdejmujemy: ");
12.   while (kopiec.Minimum(out x)) {
13.     Console.Write("{0} ", x);
14.   }
16.   Console.ReadKey();
17. }

• Kod źródłowy Implementacja