Kopce

Kopcem nazywamy pewne drzewo binarne, o pewnych ciekawych:P właściwościach. Najpierw nazewnictwo:

  • B jest ojcem A - znaczy, że B jest połączony z A, do tego B jest nad A(w sensie że jest wyżej na rysunku)
  • A jest synem B - znaczy to to samo co "B jest ojcem A"
  • korzeń(root), jest to element który nie ma żadnego ojca, znajduje się najwyżej
  • liść- element, który nie ma żadnego syna

Każdy element może mieć dwóch synów, lub być liściem. Dodatkowo może się zdarzyć, że będzie jeden(nie więcej)element z jednym synem.
Kopiec możemy przechowywać w tablicy.
Przykład poprawnego kopca(na czerwono zaznaczono numerację)

kopiec.GIF

1- jest korzeniem. Liście są od 8 do 12. Element 6 ma tylko jednego syna.

Zauważmy, że element o indeksie p ma:

  • ojca o numerze p/2(dzielenie całkowite, resztę pomijamy), jeżeli p>1
  • synów o numerach: 2p, 2p+1, jeżeli mamy takie elementy w tablicy.

Własność kopca:
Mamy 2 główne typy kopców: Min i Max
Max: Wartość ojca jest nie mniejsza od wartości jego synów
Min: Odwrotnie, wartość ojca jest nie większa od wartosci synów

przykład poprawnego kopca Max:

kopiec2.GIF

Przywracanie własności kopca:
Jeżeli wstawimy dowolny nowy element(lub zamienimy jakiś na dowolny inny), kopiec może przestać spełniać swoje własności. Trzeba to naprawić. Na naszym przykładzie załóżmy, że ktoś nam spierł dziewiąty element.
Wtedy trzeba go przenieść na opdowiednie miejsce. Najlepiej to ilustruje moja animacja(M$ Paint, cóż za wspaniały program):
(Przykład, gdy zamienimy liczbę na większą)

kopiec3.GIF

Po prostu zamieniamy miejscami marnotrawnego syna z ojcem, jeżeli synek ma większą wartość. Aż trafi na większego od siebie, albo zostanie korzeniem.

A jeżeli zmniejszymy element?
Wtedy trzeba z nim jechać w dół. Wygląda to tak:
Dopóki tata ma mniejszą wartość od swoich synów, zamieniamy go z większym(!) synem(czyli o większej wartości). I tak jedziemy, aż jego synowie
będą mieli mniejszą wartość, albo ich po prostu nie będzie(ojciec się stanie liściem).

Budowanie kopca:

Po prostu: wstawiamy nowy element, jako ostatni i przywracamy własność kopca(traktujemy takjakby to on ją zepsuł), oczywiście jeśli trzeba.

Usuwanie największego/najmniejszego elementu:
(zależy od typu kopca: max/min)
Tym skrajnym elementem jest nasz korzeń.
1. Zamieniamy go z ostatnim elementem.
2. Ten największy, co teraz jest ostatni zostaje odcięty(z kopca)
3. Naprawiamy korzeń.
Przykład:

kopiec4.gif

Przekształcenie dowolnej tablicy w kopiec:
Należy naprawić każdy element nie będący liściem przeszukując tablicę od końca. Przykład: Jeśli mamy 4000 elementów w tablicy, trzeba naprawić pierwsze 2000 w kolejności od 2000 do 1.

Sortowanie przez kopcowanie:

Należy użyć kolejki priorytetowej(czyli struktury danych, do której można wkładać elementy, oraz wyciągać z największą wartością). Tak działa sortowanie przez kopcowanie: wkłada całą tablicę do posortowania(lub przekształca ją w kopiec- nawet lepiej, bo od razu)i po kolei wyciąga maximum i odkłada jako elementy posortowane.
Do implementacji kolejki priorytetowej doskonale się nadaje właśnie kopiec.

Złożoność:
Wstawianie nowego elementu: O(log n)
Naprawa własności kopca(gdy psujemy jedną liczbę): O(log n)
Naprawa całego kopca(czyli przekształcenie tablicy w kopiec): O(n log n) O(n),
Zabranie maximum/minimum: zamiana i naprawa elementu: O(1)+O(log n)=O(log n)
Sortowanie: O(n log n+n*log n)=O(n log n)

Zalety sortowania przez kopcowienie:
Stały czas: zawsze rzędu n log n.
Brak dodatkowej pamięci(działanie w miejscu), nie potrzebuje dodatkowej pamięci do działania(pomijalnie mało)
Bo ja go lubię^^
Wady: nie podoba mi się polska nazwa;p

Widać, że kopcowanie się opłaca, na przykładzie Naszego Zakładu. Wszyscy widzieliśmy jak niedawno panowie robotniki zrobili kopce na podwórku. Widać, że jest to najpopularniejsza metoda kopania ziemi. Podobnie działają krety-kopiec kreta firmy dr etker
(nie kretyni, żeby już nikogo nie obrażać). Szukają jakichś robaków pod ziemią i … w sumie nie wiem jak to działa. Tym sie zajma biochemy.Nvm

luki92

O rany.. nie pamiętam co brałem 988 dni temu, że coś takiego wyprodukowałem. Po takim czasie zj3bały się obrazki.
Ciekawy jestem ile ludzi się przez to do tej pory przebiło.
Pozdrowienia dla ISu :)

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License