Strona główna » Algorytmy » Artykuły » Kopiec Minimalny
 

Kopiec Minimalny

https://mattomatti.com/a0213

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:

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:

CoWzór
Rodzic(i - 1) // 2
Lewy Potomek2·i + 1
Prawy Potomek2·i + 2

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:

OperacjaZłożoność
DodajO(logn)
Podejrzyj minimumO(1)
Pobierz minimumO(logn)

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.

C++C#
Python
  1. @staticmethod
  2. def Rodzic(i):
  3.   return (i - 1) // 2
  5. @staticmethod
  6. def Lewy(i):
  7.   return 2 * i + 1
  9. @staticmethod
  10. def Prawy(i):
  11.   return 2 * i + 2
  13. def __init__(self):
  14.   self.dane = []
  16. def CzyPusty(self):
  17.   return len(self.dane) == 0

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.

C++C#
Python
  1. def Dodaj(self, x):
  2.   i = len(self.dane)
  3.   self.dane.append(x)
  4.   r = KopiecMinimum.Rodzic(i)
  5.   while (i != 0 and self.dane[r] > self.dane[i]):
  6.     self.dane[i], self.dane[r] = self.dane[r], self.dane[i]
  7.     i, r = r, KopiecMinimum.Rodzic(i)

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ć.

C++C#
Python
  1. def Minimum(self):
  2.   if (self.CzyPusty()):
  3.     return None
  4.   wynik = self.dane[0]
  5.   if (len(self.dane) == 1):
  6.     self.dane = []
  7.   else:
  8.     self.dane[0] = self.dane[len(self.dane) - 1]
  9.     self.dane = self.dane[:-1]
  10.   self.Napraw()
  11.   return wynik

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:

C++C#
Python
  1. def Napraw(self, i=0):
  2.   lewy = KopiecMinimum.Lewy(i)
  3.   prawy = KopiecMinimum.Prawy(i)
  4.   imin = i
  5.   if (lewy < len(self.dane) and self.dane[lewy] < self.dane[imin]):
  6.     imin = lewy
  7.   if (prawy < len(self.dane) and self.dane[prawy] < self.dane[imin]):
  8.     imin = prawy
  9.   if (imin != i):
  10.     self.dane[i], self.dane[imin] = self.dane[imin], self.dane[i]
  11.     self.Napraw(imin)

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:

C++C#
Python
  1. kopiec = KopiecMinimum()
  2. print(" Wrzucamy: ", end="")
  3. for i in range(10):
  4.   x = (i * 17) % 10
  5.   kopiec.Dodaj(x)
  6.   print(x, end = " ")
  8. print("\nZdejmujemy: ", end="")
  9. while not kopiec.CzyPusty():
  10.   x = kopiec.Minimum()
  11.   print(x, end = " ")