algorytm.org

Kopiec (Stóg)

Pomoc
Potrzebujesz algorytmu/kodu źródłowego, którego nie znalazłeś(aś) w serwisie?
Zamów algorytm!
Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Kopiec (Stóg)
Ocena użytkowników:***** / 42
SłabyŚwietny 
Wpisany przez Andrzej Borucki, 16 sierpnia 2005 19:18

Kopiec inaczej zwany stogiem jest szczególnym przypadkiem drzewa binarnego, które spełnia tzw.warunek kopca tzn. każdy następnik jest niewiększy od swego poprzednika. Z warunku tego wynikają szczególne własności kopca:
  • w korzeniu kopca znajduje się największy lub jeden z grupy największych o identycznej wartości,
  • na ścieżkach (połączeniach między węzłami), od korzenia do liścia, elementy są posortowane nierosnąco
Oto przykładowe kopce:
kopiec zupełny kopiec niezupełny
kopiec zupełnykopiec niezupełny

Kopiec zupełny – to kopiec będący zupełnym drzewem binarnym. Drzewo binarne jest zupełne wtedy gdy wszystkie poziomy z wyjątkiem ostatniego są całkowicie zapełnione a na ostatnim liście są spójnie ułożone od strony lewej do prawej.
Na poziomie i z wyjątkiem ostatniego jest 2i węzłów
Wysokość takiego kopca jest logarytmiczna względem jego wielkości.
Kopiec zupełny można wygodnie reprezentować w tablicy o indeksie rozpoczynającym się od 1. Następniki węzła k mają numery 2k oraz 2k+1 a poprzednik węzła k ma wartość k/2 (dzielenie bez reszty - np. dla 7 rodzic ma numer 7/2 = 3).

Szczególne własności kopców zostały wykorzystane do stworzenia algorytmy do sortowania zwanego HeapSort

Kopiec pozwala również w wydajny sposób zaimplementować kolejkę priorytetową, gdzie dokładamy do niej różne elementy a wyjmujemy zawsze element największy.
Operacja wstawiania – insert
Operacja usuwania - delete max

Operacja wstawiania elementu do stosu insert:
Wstawiamy element w pierwsze wolne miejsce ostatniego poziomu, a następnie jeżeli wstawiony element jest większy od rodzica, zamieniamy go miejscami. Następnie po zamianie znów sprawdzamy, czy element jest większy od nowego rodzica. Jeżeli tak to znów zamieniamy do miejscami. Operację sprawdzania i zamieniania miejscami powtarzamy tak długo, aż w końcu rodzic będzie większy od wstawionego elementu bądź dojdziemy do korzenia.
Ponieważ wysokość kopca zupełnego jest logarytmiczna ze względu na ilość węzłów, operacja wstawiania elementu do kopca odbywa się w czasie logarytmicznym.

kopiec - wstawianie elementu - krok 1 kopiec - wstawianie elementu - krok 2 kopiec - wstawianie elementu - krok 3


Usuwanie największego elementu – delete max
Usuwamy korzeń. W miejsce korzenia wkładamy prawy skrajny liść. Wymieniamy go miejscami z większym z potomków, następnie z większym z potomków węzła w nowej pozycji. Operację wykonujemy tak długo aż obaj potomkowie będą mniejsi lub element stanie się liściem.
Ponieważ wysokość kopca zupełnego jest logarytmiczna ze względu na ilość węzłów, operacja usuwania największego elementu odbywa się również w czasie logarytmicznym.

kopiec - usuwanie elementu - krok 1 kopiec - usuwanie elementu - krok 2 kopiec - usuwanie elementu - krok 3 kopiec - usuwanie elementu - krok 4


Operacja tworzenia kopca – construct:
Wykonując ją za pomocą wielokrotnego wstawiania elementów, mielibyśmy czas O(nlog n). Daje się jednak wykonać kopiec w czasie liniowym działając rekurencyjnie na podkopcach.
Wrzucamy elementy nieuporządkowane. Procedura construct wywołuje siebie rekurencyjnie dla prawego i lewego potomka. Wówczas mamy już dwa uporządkowane podkopce. Ich rodzic niekoniecznie jest największy, więc wykonujemy tę samą procedurę przemieszczania go w stronę liścia jak przy delete max.
Testy pokazały że naiwna konstrukcja za pomocą wielokrotnego insert jest niewiele wolniejsza w przypadku wstawiania losowych liczb; znacząca różnica staje się przy niekorzystnym przypadku wstawiania kolejnych coraz większych liczb.

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Andrzej BoruckiC#
.cs
.cs
***** / 5
Marek RusinowskiC/C++Jest to klasa kopca. Oceniać :) W pliku kopiec.h znajduje się opis funkcji publicznych klasy.
.cpp
.cpp
***** / 10
Emil HotkowskiC/C++Kopiec C++
.cpp
.cpp
***** / 11
Mateusz LewkoC/C++Prosto napisany kopiec. Polecam :)
.cpp
.cpp
***** / 12
Marek RynarzewskiPhp
.php
.php
***** / 2
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 27 sierpnia 2015 07:05
Komentarze
photo
-11 # piotr 2010-02-09 00:14
Może się mylę ale o ile wiem kopiec jest drzewem binarnym a z własności tego drzewa wynika że lewe poddrzewo dowolnego wierzchołka musi zawierać elementy o mniejszej wartości.W podanym przykładzie jest odwrotnie....to chyba źle?
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+6 # Tomasz Lubiński 2010-02-13 15:04
No niestety mylisz się, mówisz o drzewie BST (algorytm.org/index.php?option=com_content&task=view&id=112&Itemid=54)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-31 # Maślana 2010-06-13 23:56
To nie jest drzewo BST! Tomasz ślepy jesteś? Lewa gałąź musi być mniejsza od korzenia a prawa większa.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+8 # Tomasz Lubiński 2010-06-14 10:19
Nigdy nie mówiłem, że kopiec przedstawiony na schemacie powyżej jest drzewem BST. Odpowiadałem tylko, że własności o których pisał Piotr posiada drzewo BST a nie kopiec.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-9 # Ciekawy 2010-06-18 14:12
A według mnie jest to kopiec ze względu na maksimum dlatego właśnie elementy lewego poddrzewa zawierają wartości mniejsze.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Mariusz Izane 2010-10-10 19:40
Ludzie czytajcie ze zrozumieniem, drzewo BST a kopiec to coś "troche" innego.
Tomasz tylko uświadamiał Piotr'a że się myli ;)
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-4 # boss 2011-01-06 20:41
mam doprowadzić drzewo do postaci kopca wiem jak zbudować kopiec mając dane elementy ale nie wiem jak uporządkować mając już je w postaci drzewa
zamieniając elementy tak aby otrzymać kopiec zaczynamy od liści czy od korzenia??
czy to nie ma znaczenia??
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # Borneq 2011-12-15 15:53
Mając kopiec nieuporządkowan y należy wywołać operację construct
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Dolores 2012-01-08 19:45
A jak jest z elementami kopca - tzn. czy mogą się powtarzać czy też kopiec to zbiór elementów parami różnych?
chodzi mi o formalną definicję i praktyczne zastosowanie...
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
0 # Michal97767 2016-01-08 21:20
a jak zbudować kopiec na podstawie tablicy ?
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz