🚀 go-pugleaf

Dnia Thu, 17 Nov 2005 22:47:43 +0100, Piotr Kobzda skrobie:
> Sektor van Skijlen wrote:
> > Dnia Thu, 17 Nov 2005 11:47:59 +0100, Miroo skrobie:
> > 
> >>Sektor van Skijlen (ethouris@pl.wp.spamu.lubie.nie.invalid)
> >>napisał(a):
> >>
> >>>najlepszym razie będzie się okazywało, że wsadzany element jest
> >>>większy od największego, więc po jednym porównaniu wyląduje na
> >>>szczycie.
> > 
> >>A ja bym powiedział, że w najlepszym razie każdy następny
> >>element jest mniejszy od najmniejszego w kopcu. Wtedy jest
> >>tylko jedno porównanie dla każdej liczby i żadnego przesuwania
> >>w kopcu (nie licząc pierwszych pięciu).
> > 
> > Nie rozumiem, dlaczego akurat się upierasz, że najmniejszy.

> Nie najmniejszy, a mniejszy (bądź równy) od najmniejszego w kopcu. 
> Algorytm Miroo zaczyna porównania zawsze od najmniejszego elementu 
> kopca. Co po zapełnieniu kopca, eliminuje potrzebę jakiejkolwiek jego 
> reorganizacji. W Twoim przypadku będzie, to niewiele, ale jednak większa 
> praca (przesunięcie, nawet gdy to tylko przewiązanie węzłów) i 
> odrzucenie ostatniego elemntu -- stąd zapewne mowa o lepszym razie.

Nie rozumiem.

Co to znaczy "po zapełnieniu kopca" i dlaczego eliminuje to potrzebę jego
reorganizacji?

Można oczywiście robić tak, że wsadzamy do kopca wszystkie wartości i robimy
sortowanie częściowe. Ale czy to jest lepsze rozwiązanie to jest już sprawa
dyskusyjna.

-- 
//  _    ___         Michal "Sektor" Malecki <sektor(whirl)kis.p.lodz.pl>
\\ L_ |/ `|  /^\ ,()                         <ethourhs(O)wp.pl>
// \_ |\  \/ \_/ /\ C++ bez cholesterolu: http://www.intercon.pl/~sektor/cbx
"I am allergic to Java because programming in Java reminds me casting spells"