A Sterta jest kompletną binarną strukturą danych drzewa, która spełnia właściwość sterty: dla każdego węzła wartość jego dzieci jest mniejsza lub równa jego własnej wartości. Sterty są zwykle używane do implementowania kolejek priorytetowych, gdzie najmniejszy (lub największy) element zawsze znajduje się w korzeniu drzewa.

Struktura danych sterty

Spis treści

• Rodzaje stosów
• Operacje na stercie
• Co to jest struktura danych sterty?

  A sterta to binarna struktura danych oparta na drzewie, która spełnia właściwość sterty: wartość każdego węzła jest większa lub równa wartości jego dzieci. Ta właściwość gwarantuje, że węzeł główny zawiera plik maksymalny Lub minimum wartość (w zależności od rodzaju sterty), a wartości zmniejszają się lub zwiększają w miarę poruszania się w dół drzewa.

  Rodzaje stosów

  Istnieją dwa główne typy kopców:

  
  
  
  
  • Maksymalna sterta: Węzeł główny zawiera wartość maksymalną, a wartości zmniejszają się w miarę przesuwania się w dół drzewa.
  • Min. sterta: Węzeł główny zawiera wartość minimalną, a wartości rosną w miarę przesuwania się w dół drzewa.

  Operacje na stercie

  Typowe operacje na stercie to:

  • Wstawić : Dodaje nowy element do sterty, zachowując właściwość sterty.
  • Wyodrębnij maks./min.: Usuwa maksymalny lub minimalny element ze sterty i zwraca go.
  • Zgromadź : Konwertuje dowolne drzewo binarne na stertę.

  Sterty są powszechnie używane do implementowania kolejek priorytetowych, w których elementy są pobierane na podstawie ich priorytetu (wartość maksymalna lub minimalna).

• Heapsort to algorytm sortowania, który wykorzystuje stertę do sortowania tablicy w kolejności rosnącej lub malejącej.
• Sterty są używane w algorytmach grafowych, takich jak Algorytm Dijkstry I Algorytm Prima do znajdowania najkrótszych ścieżek i minimalnych drzew rozpinających.

Kopia binarna

Zastosowania, zalety i wady sterty

Czas Złożoność budowy sterty

Porównanie sterty i drzewa

Czy podczas budowania sterty struktura sterty jest wyjątkowa?

Kopiec Fibonacciego

Lewicowa kupa

Kupa K-ary

Sortowanie sterty

Sprawdź, czy dane drzewo binarne jest stertem

Jak sprawdzić, czy dana tablica reprezentuje stertę binarną?

Iteracyjne sortowanie sterty

K’-ty największy element w tablicy

K’th najmniejszy/największy element w nieposortowanej tablicy | Zestaw 1

Wysokość pełnego drzewa binarnego (lub sterty) z N węzłami

Sortowanie sterty w kolejności malejącej przy użyciu minimalnej sterty

Wydrukuj wszystkie węzły mniejsze niż wartość x na stercie minimalnej.

Drzewo turniejów (drzewo zwycięzców) i sterta binarna

Połącz n lin przy minimalnych kosztach

Maksymalna liczba odrębnych elementów po usunięciu k elementów

K kombinacji maksymalnej sumy z dwóch tablic

Mediana strumienia bieżących liczb całkowitych przy użyciu STL

Mediana w strumieniu liczb całkowitych (bieżące liczby całkowite)

K’ – największy element strumienia

Największy potrójny produkt w strumieniu

Znajdź k liczb z największą liczbą wystąpień w podanej tablicy

Konwertuj minimalną stertę na maksymalną stertę

Biorąc pod uwagę kolejność poziomów drzewa binarnego, sprawdź, czy drzewo jest min-stertą

Scal k posortowanych tablic | Zestaw 1

Sortuj numery zapisane na różnych komputerach

Najmniejsze zaburzenie sekwencji

Największe zaburzenie sekwencji

Maksymalna różnica między dwoma podzbiorami m elementów

Konwertuj BST na Min. stertę

Połącz dwa binarne Max Heaps

Ciągła podtablica K-tej największej sumy

Minimalny iloczyn k liczb całkowitych w tablicy dodatnich liczb całkowitych

Zmień kolejność znaków w ciągu tak, aby żadne dwa sąsiednie nie były takie same

Suma wszystkich elementów pomiędzy najmniejszymi elementami k1’ i k2’

Minimalna suma dwóch liczb utworzonych z cyfr tablicy

Szybkie linki:

• Ćwicz problemy na stercie
• Zalecana:
  • Naucz się struktury danych i algorytmów | Poradnik DSA