Przeżycie artystyczne ;-)

Ja wiem, że dla wielu to co napiszę będzie przerażające, lub będzie dowodzić, że postradałem zmysły ;-)

Ale i tak napiszę.

Jak mi jest źle i smutno, albo gdy jestem zdenerwowany to zaczynam przeglądać źródła JDK. Np. klasy związane z kolekcjami.

Dziś by uspokoić skołatane nerwy ;-) zajrzałem do PriorityQueue. Jak dobrze zgadłem jej implementacja bazuje na kopcu.
Tak sobie czytając kod próbowałem znaleźć znajome miejsca i już w jednym z konstruktorów mamy wołanie metody heapify(), która działa ciut inaczej niż się spodziewałem (bo robi to co w Introduction to Algorithms robi BUILD-MAX-HEAP()), ale w końcu dochodzimy do kodu, który stara się przywrócić własności kopca maks, tylko że robi to ciut inaczej niżbym się tego spodziewał ;-)

Ja w swojej implementacji, tego co w ItA, używam rekurencji i mam:

void heapify(int i) {
 int l = 2*i+1;
 int r = 2*i+2;
 int largest;
 if (l<heapSize && heap[l]>heap[i]) {
  largest = l;
 } else {
  largest = i;
 }
 if (r<heapSize && heap[r]>heap[largest]) {
  largest = r;
 }
 if (i!=largest) {
  swap(i, largest);
  heapify(largest);  
 }
}

Czyli najpierw sprawdzam czy lewy syn jest większy od ojca, a później czy prawy syn jest większy od tego, który był poprzednio większy. Jeśli największy element jest różny od ojca to zamieniam je miejscami i przywracam właściwości kopca dla tego elementu.
Czyli jak w IaT stoi ;-)

Heretycy z Sun'a zrobili to jednak wbrew Słowu IaT, ale za to zrobili to sprytniej ;-)
[tutaj kod z JDK przerobiony z kopca mini na maks i z ogólnego działania na czymś używającym comparatorów na int'y, i jest to nie heapify z JDK, a odpowiednik mojego, czyli żeby przywrócić właściwości kopca to trzeba by było drania zawołać dla wszystkich od heapSize/2 do 0] :-)

void heapify(int i) {
       int half = heapSize >>> 1;
       int x = heap[i];
       while (i < half) { 
           int child = (i << 1) + 1;
           int c = heap[child];
           int right = child + 1;
           if (right < heapSize && c<heap[right])
               c = heap[child = right];
           if (x>=c)
            break;
           heap[i] = c;
           i = child;
       }
       heap[i] = x;
}

Czyż to nie jest śliczne? :-)

Pozbyli się rekurencji, co niby takie trudne nie jest, ale cały ten kod jest po prostu miły. Nie ma tam ani 1 zbędnej linijki ;-)

A co do heretyzmu Sun'owców piszących kolekcje ;-) to w TreeMap sami się przyznają, że ichnie drzewa czerwono-czarne bazują na tym jak rzecze Introduction to Algorithms ;-)


Podobne posty^beta
HeapSort, a MergeSort i QuickSort :-) - od strony "chytrości" ;-)
Koszmarne Garbage Collectory part 2 ;)
Który kod (nie kot! ;-)) lepszy?
Odrobina miłości i serwery działają ;-)
"Zostaw, zostaw. Tamtego świata się nie da uratować." - czyli syndrom Maksa