Heapsort: Heaps = ~ Quicksort: BSTs = ~ Mergesort: ___?


9

Proszę wybaczyć zwięzłość tytułu, mogłem poświęcić jasność na ołtarzu zwięzłości.

Widać, że wstawienie elementów tablicy do binarnego drzewa wyszukiwania i ich ponowne odczytanie wymaga (przy wstawianiu) takich samych porównań, jak uruchomienie Quicksort na tej tablicy. Sekwencja osi przestawnych używanych przez Quicksort to sekwencja wstawek do drzewa wyszukiwania binarnego.

Jest to również trywialnie prawdziwe w przypadku Heapsort i sterty, ponieważ Heapsort dosłownie robi taką serię wstawek, a następnie odczytuje elementy z powrotem.

Czy istnieje analog tego w przypadku powiedzmy Mergesort? Czy istnieje tutaj głębsze połączenie, czy może ciekawy zbieżność między strukturami danych a algorytmami sortowania?


1
Istnieje podobieństwo między (adaptacyjnym) MergeSort a użyciem Drzewa Wavelet, patrz citeseerx.ist.psu.edu/viewdoc/…
Jeremy

Odpowiedzi:


Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.