Elementarne struktury danych: drzewo binarne & kolejka priorytetowa

Og¢lnie rzecz bior¥c drzewo binarne to takie w kt¢rym ka¾dy element (poza korzeniem) ma ojca, oraz dw¢ch, jednego, b¥d« zero syn¢w (w takim przypadku element nazywany jest li˜ciem). Peˆne drzewo binarne to takie, w kt¢rym tylko najni¾szy poziom mo¾e by† niepeˆny, lecz owa niepeˆno˜† musi by†, ¾e tak powiem, uporz¥dkowana. To znaczy jakby rozrysowa† sobie takie drzewko, to je¾eli wyst©puje sp¢jny ci¥g element¢w od lewej strony na najni¾szym poziomie i ¾aden inny element na tym poziomie si© nie znajduje to drzewo binarne jest peˆne. 

Peˆne drzewo binarne jest wyj¥tkowo miˆ¥ struktur¥, bowiem mo¾na umie˜ci† j¥ w tablicy bez ¾adnych wska«nik¢w do syn¢w i ojc¢w, poniewa¾ mo¾na sobie offsety do nich policzy†. I tak zakˆadaj¥c ¾e korzeä jest elementem zerowym tablicy (m[0]) to maj¥c element zajmuj¥cy pozycj© x w tablicy (m[x]) mo¾emy znale«† jego ojca (m[(x-1)/2]) jego lewego syna (m[x*2+1]) i prawego (m[x*2+2]).

Z takim peˆnym drzewem binarnym mo¾emy zrobi† wiele ciekawych rzeczy. Mo¾emy zrobi† sobie z tego na przykˆad kolejk© priorytetow¥, albo napisa† oparte na nim sortowanie (dziaˆaj¥ce niby w O(nlogn), ale i tak quicksort okazuje si© zazwyczaj szybszy). Kolejka priorytetowa jest do˜† przydatn¥ struktur¥, poniewa¾ pozwala znale«† najwi©kszy element (b¥d« najmniejszy, zale¾y jak sobie j¥ napiszemy, niestety nie jest mo¾liwe szukanie min & max w jednej kolejce) w czasie O(1), mo¾na te¾ znale«† i usun¥† najwi©kszy element w czasie O(logn) i w takim samym czasie doda† nowy element. Czas logn dla 65536 wynosi po prostu 16, wi©c sami widzicie, ¾e jest to szybka i efektowna struktura. A oto przykˆadowa implementacja (akurat do wyszukiwania minimum):

class heap {
 public:
  long n, m[10000];

  void insert (long x)
  {
   m[n] = x;
   if (n>0) push_up (n);
   n++;
  }
  long delmin (void)
  {
   long tmp = m[0];
   m[0] = m[--n];
   push_down (0);
   return tmp;
  }
  long min (void)
  {
   return m[0];
  }

  void push_up (long x)
  {
   while (m[x]<m[(x-1)/2])
   {
    long tmp = m[x];
    m[x] = m[(x-1)/2];
    m[(x-1)/2] = tmp;
    if (x>0) x = (x-1)/2;
   }
  }
  void push_down (long x)
  {
   while (1)
   {
    long l=(x*2)+1;
    long r=(x*2)+2;
    long min = x;
    if ((l<n)&&(m[l]<m[min]))
     min = l;
    if ((r<n)&&(m[r]<m[min]))
     min = r;
    if (min!=x)
    {
     long tmp = m[min];
     m[min] = m[x];
     m[x] = tmp;
     x = min;
    } else break;
   }
  }
} h;

Jak wida† powy¾sza implementacja jest iteracyjna, nie rekurencyjna. Mimo ¾e wersja rekurencyjna jest du¾o, du¾o prostsza do napisania, a i raczej trudno przepeˆni† ni¥ stos (w koäcu maksymalne zagˆ©bienie si© procedury dla n element¢w wynosi lg(n), to mimo to cz©sto lepiej stosowa† wˆa˜nie wersj© iteracyjn¥. Powody? Jest szybsza. Mimo i¾ r¢¾nice mi©dzy jedn¥ a drug¥ wersj¥ s¥ minimalne, to przy wykonywaniu kilku milion¢w wywoˆaä zdejmowania/dodawania do stosu, r¢¾nica jest zauwa¾alna (tzn. wersja iteracyjna dziaˆa o par©/par©na˜cie setnych sekund szybciej, co mo¾e mie† znaczenie). Najwa¾niejsze s¥ tu dwie procedury - push_down i push_up, kt¢re sˆu¾¥ do manipulowania elementami tak, ¾eby zachowa† wˆa˜ciwo˜† stosu (tzn. w tym przypadku ¾aden z syn¢w nie mo¾e by† mniejszy od ojca). Cz©sto koduje si© je po prostu jako integralna cz©˜† procedur insert i delmin, jednak napisanie ich osobno pozwala na przywracanie wˆa˜ciwo˜ci stosu w momencie zmiany klucza dla dowolnego elementu stosu. Dziaˆanie procedury push_down jest nast©puj¥ce: sprawdzamy kt¢ry z trzech element¢w - ojca i jego dw¢ch syn¢w - jest najmniejszy. Je¾eli jest to ojciec, to wˆa˜ciwo˜ci stosu s¥ zachowane wi©c przerywamy dziaˆanie. W Przypadku, w kt¢rym jest to kt¢ry˜ z syn¢w zamieniamy go z ojcem i caˆ¥ procedur© powtarzamy tym razem dla niego. Dziaˆanie push_up polega na sprawdzaniu, czy dany element jest mniejszy od ojca. Je˜li tak, to zamieniamy go z nim i powtarzamy czynno˜ci dla ojca. Easy?:) 

nostre/marsmellow