Wdrażanie kolejki priorytetowej przy użyciu maksymalnego sterty w porównaniu ze zrównoważonym BST

Jan 25 2021

Zrównoważony BST i max heap wykonują wstawianie i usuwanie O(logn). Jednak znalezienie maksymalnej wartości w maksymalnym stosie jest, O(1)ale jest to O(logn)zrównoważone BST.

Jeśli usuniemy maksymalną wartość w maksymalnym stosie, zajmie O(logn)to, ponieważ jest to operacja usuwania.

W zbalansowanym BST, usunięcie elementu max = znalezienie maksymalnej wartości + usunięcie; równa się logn + logn redukuje się do O(logn). Więc nawet usunięcie wartości maksymalnej w zbalansowanym BST jest O(logn).

Czytałem, że jedna taka aplikacja max heap jest kolejką priorytetową i jej głównym celem jest usunięcie maksymalnej wartości dla każdej operacji usuwania z kolejki. Jeśli usunięcie elementu max dotyczy O(logn)zarówno maksymalnego sterty, jak i zbalansowanego BST, mam następujące pytania

  • Jaki jest cel maksymalnego stosu w kolejce priorytetowej tylko dlatego, że jest łatwy do wdrożenia, a nie używa pełnego przeszukiwalnego zbalansowanego BST?

  • Ponieważ nie ma obliczania współczynnika równoważenia, maksymalny stertę można nazwać niezrównoważonym drzewem binarnym?

  • Każdy zbalansowany BST może być używany jako kolejka priorytetowa i który można również przeszukiwać w przypadku, gdy wyszukiwanie O(logn)maksymalnego sterty jest O(n)poprawne?

Cały czas złożoność obliczana jest dla najgorszego przypadku. Każda pomoc jest mile widziana.

Odpowiedzi

2 trincot Jan 25 2021 at 20:05

Jaki jest cel maksymalnego stosu w kolejce priorytetowej tylko dlatego, że jest łatwy do wdrożenia, a nie używa pełnego przeszukiwalnego zbalansowanego BST?

Niektóre zalety sterty to:

  • Biorąc pod uwagę niesegregowanych szereg wejściowych, sterta wciąż może być zbudowany w O (n) w czasie , podczas gdy BST musi O (nlogn) czasu .

  • Jeśli początkowym wejściem jest tablica, ta sama tablica może służyć jako sterta, co oznacza, że ​​nie jest do niej potrzebna dodatkowa pamięć. Chociaż można by pomyśleć o sposobach stworzenia BST przy użyciu danych w tablicy, byłoby to dość dziwne (dla typów prymitywnych) i dałoby więcej narzutu przetwarzania. BST jest zwykle tworzony od zera, kopiując dane do węzłów podczas ich tworzenia.

    Ciekawostka: posortowana tablica jest również stertą, więc jeśli wiadomo, że dane wejściowe są posortowane, nic nie trzeba robić, aby zbudować stertę.

  • Sterta może być przechowywana jako tablica bez konieczności przechowywania odsyłaczy , podczas gdy BST zwykle składa się z węzłów z odniesieniami lewy i prawy. Ma to co najmniej dwie konsekwencje:

    • Pamięć używana dla BST jest około 3 razy większa niż dla stosu.
    • Chociaż kilka operacji ma tę samą złożoność czasową zarówno dla sterty, jak i BST, narzut związany z dostosowaniem BST jest znacznie większy, tak że rzeczywisty czas spędzony na tych operacjach jest (stały) współczynnik większy w przypadku BST.

Ponieważ nie ma obliczania współczynnika równoważenia, maksymalny stertę można nazwać niezrównoważonym drzewem binarnym?

Sterta jest w rzeczywistości kompletnym drzewem binarnym , więc jest zawsze tak zrównoważona, jak to tylko możliwe: liście zawsze będą umieszczone na przedostatnim lub przedostatnim poziomie. Samoczynnie równoważący się BST (taki jak AVL, czerwono-czarny, ...) nie może pokonać tak wysokiego poziomu równoważenia, w którym często pojawiają się liście na trzech poziomach lub nawet więcej.

Każdy zrównoważony BST może być używany jako kolejka priorytetowa i który jest również przeszukiwany w O (logn), jednak maksymalne wyszukiwanie sterty jest O (n) prawidłowe?

Tak to prawda. Jeśli więc aplikacja potrzebuje funkcji wyszukiwania, lepsza jest usługa BST.

2 SerejaBogolubov Jan 25 2021 at 16:53

Jaki jest cel maksymalnego stosu w kolejce priorytetowej tylko dlatego, że jest łatwy do wdrożenia, a nie używa pełnego przeszukiwalnego zbalansowanego BST?

Nie. Maksymalna sterta pasuje lepiej, ponieważ jest starannie instrumentowana, aby jak najszybciej zwrócić następny (z poszanowaniem priorytetu) element w czasie O (1). Tego chcesz od najprostszej możliwej kolejki priorytetowej.

Ponieważ nie ma obliczania współczynnika równoważenia, maksymalny stertę można nazwać niezrównoważonym drzewem binarnym?

Nie. Jest też równowaga. Krótko mówiąc, równoważenie sterty odbywa się za pomocą operacji shift-up lub shift-down (zamiana elementów, które są niesprawne).

Każdy zrównoważony BST może być używany jako kolejka priorytetowa i który jest również przeszukiwany w O (logn), jednak maksymalne wyszukiwanie sterty jest O (n) prawidłowe?

Tak! Można również użyć listy połączonej lub tablicy. Będzie to po prostu droższe pod względem notacji O i znacznie wolniejsze w praktyce.