Dlaczego sterty są lepsze niż drzewa binarne do reprezentowania kolejki priorytetowej?

Question

W sterty (maks.) Łatwo jest znaleźć największy element w czasie O(1), ale aby go usunąć, potrzebna jest złożoność O(log(n)).

Więc jeśli wstawianie i usuwanie ze sterty jest zarówno O(log(n)), jakie są zalety sterty nad drzewem binarnym do reprezentowania kolejki priorytetowej?

Answer 1

1. Stosy zużywają mniej pamięci. Mogą być zaimplementowane jako tablice, a zatem nie ma narzutu do przechowywania wskaźników. (Drzewo binarne MOŻE być zaimplementowane jako tablica, ale prawdopodobnie istnieje wiele pustych "luk", które mogą zmarnować jeszcze więcej miejsca niż implementowanie ich jako węzłów ze wskaźnikami).

2. Stosy mają wysokość kłody (n), ponieważ nie muszą gwarantować, że elementy mogą być pobierane w porządku posortowanym, chociaż są wykonywane w kolejności, tylko że wartość węzła dominuje w wartościach dla dzieci. To pozwala im mieć "spakowaną" strukturę jako tablicę. Drzewo binarne (chyba że jest to zbalansowane drzewo binarne) zwykle kończy się na gałęziach, których wysokość jest większa niż log (n), więc nawet jeśli operacje mają taką samą dużą złożoność O, w rzeczywistości stertę będzie nieco szybciej.

3. Ponieważ stertę można zaimplementować jako tablicę, uzyskuje się ogromną zaletę dostępu do ciągłej pamięci, która prawdopodobnie nadal znajduje się w pamięci podręcznej, zamiast dostępu do węzłów wskazanych przez wskaźniki, których pamięć jest rozproszona w każdym miejscu.

4. Stosy są prostsze do wykonania niż drzew binarnych (szczególnie wyważone drzewo binarne)

Wadą jest to, że z hałdy nie jesteś w stanie zrobić wyszukiwania binarnego, ale dla kolejki priorytetowej nie robić potrzebuję tej umiejętności.