Sterta (struktura danych) - Heap (data structure)
W informatyce , A kupa jest wyspecjalizowanym drzewo -na struktura danych , która jest w zasadzie prawie pełne drzewo spełniającym własności sterty : w maks sterty , dla danego węzła C, jeśli P jest węzeł nadrzędny C, a następnie klawisz ( wartość ) P jest większa lub równa kluczowi C. W kopcu min , klucz P jest mniejszy lub równy kluczowi C. Węzeł na „szczycie” sterty (bez rodziców) nazywa się węzłem głównym .
Sterta jest jedną maksymalnie wydajną implementacją abstrakcyjnego typu danych zwanego kolejką priorytetową , aw rzeczywistości kolejki priorytetowe są często określane jako „sterty”, niezależnie od tego, jak mogą być zaimplementowane. W stercie element o najwyższym (lub najniższym) priorytecie jest zawsze przechowywany w katalogu głównym. Jednak sterta nie jest posortowaną strukturą; można go uznać za częściowo zamówiony. Sterta jest użyteczną strukturą danych, gdy konieczne jest wielokrotne usuwanie obiektu o najwyższym (lub najniższym) priorytecie.
Typową implementacją sterty jest sterta binarna , w której drzewo jest drzewem binarnym (patrz rysunek). Struktura danych stos, zwłaszcza sterty binarny, został wprowadzony przez JWJ Williams, 1964, jako struktura danych dla sortowanie przez kopcowanie algorytmu sortowania. Sterty są również kluczowe w kilku wydajnych algorytmach grafowych, takich jak algorytm Dijkstry . Gdy stos jest pełne drzewo binarne, ma najmniejszą możliwą wysokość sterty z N węzłów i dla każdego węzła a gałęzie zawsze zalogować się N wysokość.
Zauważ, że, jak pokazano na rysunku, nie ma dorozumianej kolejności między rodzeństwem lub kuzynami i nie ma dorozumianej sekwencji przechodzenia w kolejności (jak miałoby to miejsce np. w binarnym drzewie wyszukiwania ). Wspomniana powyżej relacja sterty dotyczy tylko węzłów i ich rodziców, dziadków itp. Maksymalna liczba dzieci, które może mieć każdy węzeł, zależy od typu sterty.
Operacje
Typowe operacje na hałdach to:
- Podstawowy
- find-max (lub find-min ): znajdź odpowiednio maksymalną pozycję max-sterty lub minimalną pozycję min-heap (aka peek )
- insert : dodanie nowego klucza do sterty (aka, push )
- extract-max (lub extract-min ): zwraca węzeł o maksymalnej wartości ze sterty max [lub wartości minimalnej ze sterty min] po usunięciu go ze sterty (aka, pop )
- delete-max (lub delete-min ): usuwanie węzła głównego z max sterty (lub min sterty), odpowiednio
- zastąpić : pop root i wcisnąć nowy klawisz. Bardziej wydajne niż pop, a następnie push, ponieważ wystarczy balansować tylko raz, a nie dwa razy i odpowiednie dla stert o stałej wielkości.
- kreacja
- create-heap : utwórz pustą stertę
- heapify : utwórz stertę z podanej tablicy elementów
- merge ( union ): łączenie dwóch stert w celu utworzenia poprawnej nowej sterty zawierającej wszystkie elementy obu, zachowując oryginalne sterty.
- meldunek : łączenie dwóch stert w celu utworzenia ważnej nowej sterty zawierającej wszystkie elementy obu, niszcząc oryginalne sterty.
- Kontrola
- size : zwraca liczbę elementów w stercie.
- is-empty : zwraca prawdę, jeśli sterta jest pusta, w przeciwnym razie fałsz.
- Wewnętrzny
- klucz wzrostu lub klucz zmniejszania : aktualizowanie klucza odpowiednio w ramach max- lub min-heap
- delete : usuń dowolny węzeł (następnie przesuwając ostatni węzeł i przesiewając w celu utrzymania sterty)
- sift-up : przenieś węzeł w górę drzewa tak długo, jak to konieczne; służy do przywracania stanu sterty po wstawieniu. Nazywany „sift”, ponieważ węzeł przesuwa się w górę drzewa, aż osiągnie właściwy poziom, jak w sicie .
- sift-down : przenieś węzeł w dół drzewa, podobnie jak przesiać; służy do przywracania stanu sterty po usunięciu lub zastąpieniu.
Realizacja
Sterty są zwykle implementowane za pomocą tablicy , w następujący sposób:
- Każdy element tablicy reprezentuje węzeł sterty, a
- Relacja rodzic/dziecko jest definiowana niejawnie przez indeksy elementów w tablicy.
W przypadku sterty binarnej w tablicy pierwszy indeks zawiera element główny. Następne dwa indeksy tablicy zawierają dzieci korzenia. Następne cztery indeksy zawierają czworo dzieci z dwóch węzłów podrzędnych korzenia i tak dalej. Zatem dany węzeł o indeksie i , jego dzieci mają indeksy 2i + 1 i 2i + 2 , a rodzic ma indeks ⌊(i−1)/2⌋ . Ten prosty schemat indeksowania umożliwia efektywne przesuwanie „w górę” lub „w dół” drzewa.
Równoważenie sterty odbywa się poprzez operacje przesiewania lub przesiewania (wymiana elementów, które nie działają). Ponieważ możemy zbudować stertę z tablicy bez potrzeby dodatkowej pamięci (na przykład dla węzłów), heapsort może być użyty do sortowania tablicy w miejscu.
Po wstawieniu elementu do sterty lub usunięciu ze sterty właściwość sterty może zostać naruszona, a sterta musi zostać ponownie zrównoważona przez zamianę elementów w tablicy.
Chociaż różne typy stert różnie realizują operacje, najczęstszy sposób jest następujący:
Wstawianie: Dodaj nowy element na końcu sterty, w pierwszym dostępnym wolnym miejscu. Naruszy to właściwość sterty, więc elementy są przesuwane w górę (lub operacja pływania ), dopóki właściwość sterty nie zostanie przywrócona.
Wyodrębnianie: Usuń korzeń i wstaw ostatni element sterty do katalogu głównego, a to naruszy właściwość sterty, więc przesiaj w dół, aby ponownie ustanowić właściwość sterty (lub operację ujścia ). Tak więc zastępowanie odbywa się poprzez usunięcie korzenia i umieszczenie nowego elementu w korzeniu i przesianie w dół, unikając kroku przesiewania w górę w porównaniu z pop (przesiewanie ostatniego elementu), a następnie push (przesiewanie nowego elementu).
Konstrukcję kopca binarnego (lub d- arnego) z zadanej tablicy elementów można wykonać w czasie liniowym przy użyciu klasycznego algorytmu Floyda , z najgorszą liczbą porównań równą 2 N − 2 s 2 ( N ) − e 2 ( N ) (dla stosu binarnego), gdzie s 2 ( N ) jest sumą wszystkich cyfr reprezentacji binarnej N , a e 2 ( N ) jest wykładnikiem 2 w faktoryzacji pierwszej N . Jest to szybsze niż sekwencja kolejnych wstawień do pierwotnie pustej sterty, która jest logarytmicznie liniowa.
Warianty
Porównanie granic teoretycznych dla wariantów
Oto złożoność czasowa różnych struktur danych sterty. Nazwy funkcji zakładają maksymalną stertę. Aby poznać znaczenie „ O ( f )” i „ Θ ( f )” zobacz notację Big O .
| Operacja | znajdź-max | usuń-max | wstawić | klawisz zwiększania | łączyć |
|---|---|---|---|---|---|
| Dwójkowy | Θ (1) | Θ (log n ) | O (log n ) | O (log n ) | Θ ( n ) |
| Lewicowy | Θ (1) | Θ (log n ) | Θ (log n ) | O (log n ) | Θ (log n ) |
| Dwumianowy | Θ (1) | Θ (log n ) | Θ (1) | Θ (log n ) | O (log n ) |
| Fibonacciego | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Łączenie w pary | Θ (1) | O (log n ) | Θ (1) | o (log n ) | Θ (1) |
| Brodal | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Parowanie rang | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| Ścisły Fibonacci | Θ (1) | O (log n ) | Θ (1) | Θ (1) | Θ (1) |
| 2-3 stosy | O (log n ) | O (log n ) | O (log n ) | Θ (1) | ? |
Aplikacje
Struktura danych sterty ma wiele zastosowań.
- Heapsort : Jedna z najlepszych metod sortowania na miejscu i bez kwadratowego najgorszego scenariusza.
- Algorytmy wyboru : sterta umożliwia dostęp do elementu min lub max w stałym czasie, a inne selekcje (takie jak mediana lub k-ty element) mogą być dokonywane w czasie podliniowym na danych znajdujących się w stercie.
- Algorytmy wykresów : Używając stert jako wewnętrznych struktur danych przechodzenia, czas wykonywania zostanie skrócony o porządek wielomianowy. Przykładami takich problemów są algorytm minimalnego drzewa opinającego Prima i algorytm najkrótszej ścieżki Dijkstry .
- Kolejka priorytetowa : Kolejka priorytetowa jest pojęciem abstrakcyjnym, takim jak „lista” lub „mapa”; tak jak lista może być zaimplementowana z połączoną listą lub tablicą, kolejka priorytetowa może być zaimplementowana za pomocą sterty lub wielu innych metod.
- Scalanie K-way : Struktura danych sterty jest przydatna do scalania wielu już posortowanych strumieni wejściowych w jeden posortowany strumień wyjściowy. Przykłady potrzeby scalania obejmują sortowanie zewnętrzne i przesyłanie strumieniowe wyników z danych rozproszonych, takich jak drzewo scalania o strukturze dziennika. Wewnętrzna pętla uzyskuje element min, zastępując go następnym elementem dla odpowiedniego strumienia wejściowego, a następnie wykonuje operację przesiewania sterty. (Alternatywnie funkcja replace.) (Korzystanie z funkcji extract-max i insert z kolejki priorytetowej jest znacznie mniej wydajne.)
- Statystyka zamówień : Struktury danych sterty można użyć do efektywnego znalezienia k-tego najmniejszego (lub największego) elementu w tablicy.
Implementacje języka programowania
- C ++ Standardowa biblioteka zapewnia make_heap , push_heap i pop_heap algorytmy hałd (zwykle realizowany jako kopiec binarny), które działają na arbitralnych swobodnym dostępie iteratorów . Traktuje iteratory jako odwołanie do tablicy i używa konwersji tablicy na stertę. Udostępnia również adapter kontenera priority_queue , który opakowuje te udogodnienia w klasę podobną do kontenera. Jednak nie ma standardowej obsługi operacji zamiany, przesiewania/przesiewania lub zmniejszania/zwiększania klawiszy.
- Biblioteki Boost C++ zawierają bibliotekę sterty. W przeciwieństwie do STL, obsługuje operacje zmniejszyć lub zwiększyć, i obsługuje dodatkowe rodzaje sterty: konkretnie, obsługuje d -ary, dwumianowy, Fibonacciego, parowanie i pochylenie stert.
- Istnieje ogólna implementacja sterty dla C i C++ z obsługą sterty D-ary i sterty B. Zapewnia interfejs API podobny do STL.
- Standardowa biblioteka języka programowania D zawiera std.container.BinaryHeap , który jest zaimplementowany w zakresie zakresów D . Instancje mogą być tworzone z dowolnego zakresu o dostępie swobodnym . BinaryHeap udostępnia interfejs zakresu wejściowego, który umożliwia iterację za pomocą wbudowanych instrukcji foreach D i integrację z interfejsem API opartym na zakresach pakietu std.algorithm .
- Java platformy (od wersji 1.5) zapewnia realizację binarny sterty z klasą
java.util.PriorityQueuew kolekcje Java Framework . Ta klasa domyślnie implementuje min-stertę; aby zaimplementować stertę max, programista powinien napisać własny komparator. Nie ma obsługi operacji zamiany, przesiewania/przesiewania lub zmniejszania/zwiększania klawiszy. - Python ma moduł heapq , który implementuje kolejkę priorytetową przy użyciu sterty binarnej. Biblioteka udostępnia funkcję heapreplace do obsługi scalania k-way.
- PHP ma zarówno stertę maksymalną ( SplMaxHeap ), jak i min-stertę ( SplMinHeap ) od wersji 5.3 w standardowej bibliotece PHP.
- Perl ma implementacje stert binarnych, dwumianowych i Fibonacciego w dystrybucji Heap dostępnej na CPAN .
- Język Go zawiera pakiet sterty z algorytmami sterty, które działają na dowolnym typie spełniającym dany interfejs. Ten pakiet nie obsługuje operacji zamiany, przesiewania/przesiewania ani zmniejszania/zwiększania klawiszy.
- Biblioteka Core Foundation firmy Apple zawiera strukturę CFBinaryHeap .
- Pharo ma implementację sterty w pakiecie Collections-Sequenceable wraz z zestawem przypadków testowych. Sterta jest używana w implementacji pętli zdarzeń czasomierza.
- Język programowania Rust ma binarną implementację max-heap, BinaryHeap , w module kolekcji swojej standardowej biblioteki.
Zobacz też
- Algorytm sortowania
- Wyszukaj strukturę danych
- Stos (abstrakcyjny typ danych)
- Kolejka (abstrakcyjny typ danych)
- Drzewo (struktura danych)
- Treap , forma binarnego drzewa wyszukiwania opartego na drzewach uporządkowanych na stercie
Bibliografia
Zewnętrzne linki
- Kupa w Wolfram MathWorld
- Wyjaśnienie działania podstawowych algorytmów sterty
- Bentley, Jon Louis (2000). Perły programowania (wyd. 2). Addisona Wesleya. s. 147-162. Numer ISBN 0201657880.