Samouczek struktury danych sterty
Ilustracja struktur danych sterty
Istnieją dwa rodzaje sterty: maksymalny. Struktura maksymalna jest miejscem, w którym maksymalna wartość to root, a wartości stają się mniejsze w miarę opadania drzewa; Każdy rodzic jest równy lub większy niż którekolwiek z jego najbliższych dzieci. Struktura minimalna jest miejscem, w którym minimalna wartość jest korzeniem, a wartości stają się większe w miarę zstąpienia drzewa; Każdy rodzic jest równy lub mniejszy niż którekolwiek z jego najbliższych dzieci. Na poniższych schematach pierwsza to maksymalna heap, a drugi to minimalny heap:
W przypadku obu stosów zauważ, że dla pary dzieci nie ma znaczenia, czy ten po lewej stronie jest większą wartością. Rząd na poziomie na drzewie, niekoniecznie musi być wypełniony od minimum do maksimum, od lewej; niekoniecznie jest również wypełniony od maksimum do minimum, od lewej.
Reprezentując stos w tablicy
Aby oprogramowanie łatwo korzystać z sterty, sterta musi być reprezentowana w tablicy. Max-heap powyżej, reprezentowany w tablicy to:
89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69Odbywa się to od wartości głównej jako pierwszej wartości dla tablicy. Wartości są ciągle umieszczane przez odczyt drzewa od lewej do prawej, od góry do dołu. Jeśli element jest nieobecny, jego pozycja w tablicy jest pomijana. Każdy węzeł ma dwoje dzieci. Jeśli węzeł jest w indeksie (pozycji) n, jego pierwsze dziecko w tablicy jest w indeksie 2n+1, a jego następne dziecko jest w indeksie 2n+2. 89 jest w indeksie 0; Jego pierwsze dziecko, 85 jest w indeksie 2 (0)+1 = 1, podczas gdy jego drugie dziecko jest w indeksie 2 (0)+2 = 2. 85 jest w indeksie 1; jego pierwsze dziecko, 84, jest w indeksie 2 (1)+1 = 3, podczas gdy jego drugie dziecko, 82 jest w indeksie 2 (1)+2 = 4. 79 jest w indeksie 5; Jego pierwsze dziecko, 65 jest w indeksie 2 (5)+1 = 11, podczas gdy jego drugie dziecko jest w indeksie 2 (5)+2 = 12. Formuły są stosowane do reszty elementów w tablicy.
Taka tablica, w której znaczenie elementu i związku między elementami jest implikowane przez pozycję elementu, nazywa się niejawną strukturą danych.
Niejawna struktura danych dla powyższego minimum jest:
65, 68, 70, 73, 71, 83, 84 ,,, 79, 80 ,, 85, 89Powyższy maksymalnie jest kompletnym drzewem binarnym, ale nie pełnym drzewem binarnym. Dlatego niektóre lokalizacje (pozycje) są puste w tablicy. Aby uzyskać pełne drzewo binarne, w tablicy żadna lokalizacja nie będzie pusta.
Teraz, gdyby stos był prawie kompletnym drzewem, na przykład, gdyby brakuje wartości 82, tablica byłaby:
89, 85, 87, 84 ,, 79, 73, 80, 81 ,, 65, 69W tej sytuacji trzy lokalizacje są puste. Jednak formuły są nadal obowiązujące.
Operacje
Struktura danych jest formatem danych (e.G. drzewo) plus związek między wartościami, a także operacje (funkcje) działają na wartościach. W przypadku sterty relacja, która przebiega przez całą stos, jest to, że rodzic musi mieć równą lub większą wartość niż dzieci, dla maksimum; a rodzic musi być równy lub mniejszy niż dzieci. Ten związek nazywa się właściwością sterty. Operacje sterty są pogrupowane pod nagłówkami tworzenia, podstawowego, wewnętrznego i kontroli. Następuje podsumowanie operacji sterty:
Podsumowanie operacji sterty
Istnieją pewne operacje oprogramowania, które są wspólne dla stosów, w następujący sposób:
Tworzenie sterty
create_Heap: Tworzenie sterty oznacza tworzenie obiektu reprezentującego stertę. W języku C możesz utworzyć stertę z typem obiektu struct. Jednym z członków struktury będzie tablica sterty. Reszta członków będzie funkcjami (operacjami) dla stertu. Utwórz_heap oznacza utworzenie pustej sterty.
Uprawy: tablica sterty jest częściowo posortowana (uporządkowana) tablica. Załóż środki, podaj tablicę sterty z niepotrzebnej tablicy - patrz szczegóły poniżej.
Scal: Oznacza to, tworząc stos związków z dwóch różnych stosów - patrz szczegóły poniżej. Dwie heaps powinny być maksymalne lub oba minimalne. Nowa sterta jest zgodna z właściwością sterta, podczas gdy oryginalne sterty są zachowane (nie wymazane).
MELD: Oznacza to, że dołącz do dwóch stosów tego samego typu, aby utworzyć nowy, utrzymując duplikaty - patrz szczegóły poniżej. Nowa sterta jest zgodna z właściwością sterty, podczas gdy oryginalne sterty są niszczone (wymazane). Główną różnicą między scalaniem a połączeniem jest to, że dla połączenia jedno drzewo pasuje jako poddrzewa do korzenia drugiego drzewa, umożliwiając duplikaty wartości w nowym drzewie, podczas gdy do scalania powstaje nowe drzewo sterty, usuwając duplikaty. Nie ma potrzeby utrzymywania dwóch oryginalnych stosów z połączeniem.
Podstawowe operacje sterty
Find_max (Find_min): Znajdź maksymalną wartość w tablicy maksymalnej i zwróć kopię lub zlokalizuj minimalną wartość w tablicy min-heap i zwróć kopię.
Wstaw: Dodaj nowy element do tablicy sterty i zmienił tablicę, aby utrzymywano właściwość sterty schematu.
Extract_max (Extract_min): Znajdź maksymalną wartość w tablicy maksymalnej, usuń ją i zwróć; lub zlokalizuj minimalną wartość w tablicy min-heap, usuń ją i zwróć.
delete_max (delete_min): zlokalizuj węzeł główny maksymalnego heap, który jest pierwszym elementem tablicy maksymalnej, usuń go bez konieczności zwracania go; lub zlokalizuj węzeł główny minimalnej grupy, który jest pierwszym elementem tablicy min-heap, usuń go bez konieczności zwracania go;
Wymień: zlokalizuj węzeł główny dowolnej sterty, wyjmij go i wymień na nowy. Nie ma znaczenia, czy stary korzeń jest zwracany.
Wewnętrzne operacje sterty
wzrost_key (spadek_key): Zwiększ wartość dowolnego węzła dla maksymalnego heap i przemieszczenia, aby właściwość sterty była utrzymywana lub zmniejszyć wartość dowolnego węzła dla minima i zmieniającego się, aby właściwość sterty była utrzymywana.
Usuń: usuń dowolny węzeł, a następnie zmień zmianę, tak aby właściwość sterta była utrzymywana dla maksymalnego healu lub minimum.
Shift_up: Porusz węzeł w górę w maksymalnym lub minimalnym heat.
shift_down: przesuń węzeł w dół w maksymalnym lub minimalnym heat.
Kontrola sterty
Rozmiar: Zwraca to liczbę kluczy (wartości) w sterce; Nie obejmuje pustych lokalizacji tablicy sterty. Sterta może być reprezentowana przez kod, jak na schemacie lub za pomocą tablicy.
jest pusty: Zwraca to boolean, jeśli nie ma węzła w stercie lub logicznie false, jeśli stos ma co najmniej jeden węzeł.
Przesiewanie w stosie
Jest Sift-up i Sift Down:
Sift-up: Oznacza to zamian węzła z jego rodzicem. Jeśli właściwość sterta nie jest zadowolona, zamień rodzica na własnego rodzica. Kontynuuj tę drogę na ścieżce, aż właściwość sterty nie zostanie spełniona. Procedura może dotrzeć do korzenia.
Przesieć: Oznacza to wymianę węzła o dużej wartości z mniejszym z dwojga dzieci (lub jednym dzieckiem na prawie kompletną stos). Jeśli właściwość sterta nie jest zadowolona, zamień dolny węzeł za mniejszym węzłem własnego dzieci. Kontynuuj tę drogę na ścieżce, aż właściwość sterty nie zostanie spełniona. Procedura może osiągnąć liść.
Rozwój
Awdata oznacza sortować nieposortowaną tablicę, aby właściwość sterty była zadowolona z maksymalnego lub min-heap. Oznacza to, że w nowej tablicy mogą być puste lokalizacje. Podstawowy algorytm do rozliczania maksymalnego lub min-heap jest następujący:
- Jeśli węzeł główny jest bardziej ekstremalny niż którykolwiek z węzła jego dziecka, wymieniaj korzeń z mniej ekstremalnym węzłem dziecięcym.
- Powtórz ten krok z węzłami dziecięcymi w przedsprzedażowym schemacie przejścia na drzewo.
Ostateczne drzewo jest kupą satysfakcjonującą właściwość sterty. Sterta może być reprezentowana jako schemat drzewa lub w tablicy. Powstała sterta to częściowo posortowane drzewo, tj.mi. Częściowo posortowana tablica.
Szczegóły operacji sterty
W niniejszej sekcji artykułu zawiera szczegóły operacji sterty.
Tworzenie szczegółów sterty
create_heap
Patrz wyżej!
Rozprzyj
Patrz wyżej
łączyć
Jeśli tablice sterty,
89, 85, 87, 84, 82, 79, 73, 80, 81 ,, 65, 69I
89, 85, 84, 73, 79, 80, 83, 65, 68, 70, 71są połączone, może być wynik bez duplikatów,
89, 85, 87, 84, 82, 83, 81, 80, 79, 73, 68, 65, 69, 70, 71Po jakimś przesiewaniu. Zauważ, że w pierwszej tablicy 82 nie ma dzieci. W wynikowej tablicy jest to indeks 4; a jego lokalizacje w indeksie 2 (4)+1 = 9 i 2 (4)+2 = 10 są puste. Oznacza to, że nie ma również dzieci na nowym schemacie drzewa. Oryginalne dwie stosy nie powinny być usuwane, ponieważ ich informacje nie są tak naprawdę w nowej stercie (nowa tablica). Podstawowy algorytm do scalania stosów tego samego typu jest następujący:
- Dołącz do jednej tablicy na dole drugiej tablicy.
- Handpify eliminuje duplikaty, upewniając się, że węzły, które nie miały dzieci w oryginalnych stosach, nadal nie mają dzieci w nowej stercie.
Meld
Algorytm do połączenia dwóch stosów tego samego typu (dwa maksymalne lub dwa min-) jest następujące:
- Porównaj dwa węzły główne.
- Zrób mniej ekstremalny korzeń i resztę jego drzewa (poddrzewa), drugie dziecko ekstremalnego korzenia.
- Siuj zbłąkane dziecko korzenia teraz ekstremalnego poddrzew, w dół w skrajnym poddrzewaniu.
Powstała stos jest nadal zgodna z właściwością sterty, podczas gdy oryginalne sterty są niszczone (wymazane). Oryginalne stosy można zniszczyć, ponieważ wszystkie posiadane informacje są nadal w nowej stercie.
Podstawowe operacje sterty
Find_max (Find_min)
Oznacza to zlokalizowanie maksymalnej wartości w tablicy maksymalnej i zwrócić kopię lub zlokalizować minimalną wartość w tablicy min-heap i zwrócić kopię. Z definicji tablica sterty już zaspokaja właściwość Heap. Po prostu zwróć kopię pierwszego elementu tablicy.
wstawić
Oznacza to dodanie nowego elementu do tablicy sterty i zmień zmianę tablicy, aby zachować właściwość sterty diagramu (zadowolona). Algorytm do zrobienia dla obu rodzajów sterty jest następujący:
- Przyjmij pełne drzewo binarne. Oznacza to, że tablica musi być wypełniona na końcu pustymi lokalizacjami, jeśli to konieczne. Całkowita liczba węzłów pełnej sterty wynosi 1 lub 3 lub 7 lub 15 lub 31 itp.; Podwajaj i dodaj 1.
- Umieść węzeł w najbardziej odpowiednim pustym miejscu według wielkości, pod koniec stosu (pod koniec tablicy sterty). Jeśli nie ma pustej lokalizacji, rozpocznij nowy wiersz od lewej dolnej części.
- W razie potrzeby przesiać, dopóki właściwość sterta nie zostanie spełniona.
ekstrakt_max (ekstrakt_min)
Znajdź maksymalną wartość w tablicy maksymalnej, usuń ją i zwróć; lub zlokalizuj minimalną wartość w tablicy min-heap, usuń ją i zwróć. Algorytm do ekstraktu_max (Extract_min) jest następujący:
- Usuń węzeł główny.
- Weź (usuń) dolny prawy węzeł (ostatni węzeł w tablicy) i umieść w korzeni.
- Przesiać odpowiednio, dopóki właściwość sterta nie zostanie spełniona.
delete_max (delete_min)
Znajdź węzeł główny maksymalnego heap, który jest pierwszym elementem tablicy maksymalnej, usuń go bez konieczności zwracania go; lub zlokalizuj węzeł główny minimalnej grupy, który jest pierwszym elementem tablicy min-heap, usuń go bez konieczności zwracania. Algorytm usuwania węzła głównego jest następujący:
- Usuń węzeł główny.
- Weź (usuń) dolny prawy węzeł (ostatni węzeł w tablicy) i umieść w korzeni.
- Przesiać odpowiednio, dopóki właściwość sterta nie zostanie spełniona.
zastępować
Znajdź węzeł główny dowolnej sterty, usuń go i wymień na nowy. Nie ma znaczenia, czy stary korzeń jest zwracany. W razie potrzeby przesiać, aż do spełnienia właściwości sterty.
Wewnętrzne operacje sterty
wzrost_key (spadek_key)
Zwiększ wartość dowolnego węzła dla maksymalnego heap i zmienia się, aby właściwość sterty była utrzymywana lub zmniejszyć wartość dowolnego węzła dla min-heap i zmiany, aby zachować właściwość sterty. Przesiać w górę lub w dół, odpowiednio, dopóki właściwość sterta nie zostanie spełniona.
usuwać
Usuń węzeł zainteresowania, a następnie zmień zmianę, tak aby właściwość sterty była utrzymywana dla maksymalnego healu lub min-heap. Algorytm usuwania węzła jest następujący:
- Usuń węzeł zainteresowania.
- Weź (usuń) dolny w prawo węzeł (ostatni węzeł w tablicy) i umieść w indeksie usuniętego węzła. Jeśli usunięty węzeł jest w ostatnim rzędzie, może to nie być konieczne.
- Przesiać w górę lub w dół, odpowiednio, dopóki właściwość sterta nie zostanie spełniona.
przesunięcie w górę
Przenieś węzeł w górę w maksymalnym lub minimalnym poziomie, tak długo, jak to konieczne, przestawiając się w celu utrzymania właściwości sterty-Sift Up.
Bieg w dół
Przesuń węzeł w dół w maksymalnej lub minimalnej grupie, tak długo, jak to konieczne, przestawiając się w celu utrzymania właściwości sterty-Sift Down.
Kontrola sterty
rozmiar
Patrz wyżej!
jest pusty
Patrz wyżej!
Inne klasy stosów
Sterta opisana w tym artykule można uznać za główną (ogólną) stertę. Istnieją inne klasy stosów. Jednak te dwa, o których powinieneś wiedzieć poza tym, to sterta binarna i sterta D-ary.
Sterta binarna
Sterta binarna jest podobna do tej głównej sterty, ale z większymi ograniczeniami. W szczególności sterta binarna musi być kompletnym drzewem. Nie myl między pełnym drzewem a pełnym drzewem.
sterta D-ary
Sterta binarna to 2-ary heap. Sterta, w której każdy węzeł ma 3 dzieci, ma 3-ary stopę. Sterta, w której każdy węzeł ma 4 dzieci, ma stos 4-ary i tak dalej. Sterta d-ary ma inne ograniczenia.
Wniosek
Sterta to kompletne lub prawie kompletne drzewo binarne, które spełnia właściwość sterty. Właściwość sterta ma 2 alternatywy: w przypadku maksymalnego heap rodzic musi mieć wartość równą lub większą niż najbliższe dzieci; W przypadku minimum rodzic musi być równy lub mniejszy niż dzieci bezpośrednio. Sterta może być reprezentowana jako drzewo lub w tablicy. Po reprezentowaniu w tablicy węzeł główny jest pierwszym węzłem tablicy; a jeśli węzeł znajduje się w indeksie N, jego pierwsze dziecko w tablicy jest w indeksie 2n+1, a jego następne dziecko znajduje się w indeksie 2n+2. Sterta ma pewne operacje wykonywane w tablicy.
Chrys