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. private:
2.   vector<int> dane;
4. public:
5.   int Rodzic(int i) {
6.     return (i - 1) / 2;
7.   }
9.   int Lewy(int i) {
10.     return 2 * i + 1;
11.   }
13.   int Prawy(int i) {
14.     return 2 * i + 2;
15.   }
17.   bool CzyPusty() {
18.     return dane.size() == 0;
19.   }

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. void Dodaj(int x) {
2.   int i = dane.size();
3.   dane.push_back(x);
4.   while (i != 0 && dane[Rodzic(i)] > dane[i])
5.   {
6.     swap(dane[i], dane[Rodzic(i)]);
7.     i = Rodzic(i);
8.   }
9. }

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. bool Minimum(int& wynik) {
2.   if (CzyPusty()) {
3.     return false;
4.   }
5.   wynik = dane[0];
6.   if (dane.size() == 1) {
7.     dane.clear();
8.   }
9.   else {
10.     dane[0] = dane[dane.size() - 1];
11.     dane.erase(dane.end() - 1, dane.end());
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. {
3.   int lewy = Lewy(i);
4.   int prawy = Prawy(i);
5.   int imin = i;
6.   if (lewy < dane.size() && dane[lewy] < dane[imin]) {
7.     imin = lewy;
8.   }
9.   if (prawy < dane.size() && dane[prawy] < dane[imin]) {
10.     imin = prawy;
11.   }
12.   if (imin != i)
13.   {
14.     swap(dane[i], dane[imin]);
15.     Napraw(imin);
16.   }
17. }

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. int main() {
2.   KopiecMinimum kopiec;
3.   int x;
4.   cout << " Wrzucamy: ";
5.   for (int i = 0; i < 10; i++) {
6.     x = (i * 17) % 10;
7.     kopiec.Dodaj(x);
8.     cout << x << " ";
9.   }
11.   cout << "\nZdejmujemy: ";
12.   while (kopiec.Minimum(x)) {
13.     cout << x << " ";
14.   }
16.   system("pause");
17.   return 0;
18. }

• Kod źródłowy Implementacja