Heapsort: dlaczego nie użyć "Soft Heap", aby zwiększyć wydajność?

Question

Wydaje się, że ze strony wikipedii w wersji Soft Heap minimalne wydobycie zajmuje tylko stały czas, dlatego użycie miękkiego sterty do wykonania heapsortu powinno prowadzić do zamortyzowanego O (n). Nawet jeśli stała jest duża, dla bardzo dużego n ten algorytm powinien być bardzo użyteczny. Ale nigdy nie słyszałem, żeby ludzie o tym wspominali. Czy istnieje powód, dla którego ludzie tego nie używają?

Dzięki!

Answer 1

Miękki stert cierpi z powodu "korupcji" (przeczytaj stronę, do której prowadzi łącze), co sprawia, że ​​nie można go zastosować jako elementu ogólnego procesu sortowania. Po prostu otrzymasz błędną odpowiedź przez większość czasu.

Jeśli masz jakąś aplikację, która wymaga sortowania, ale może uporać się z "uszkodzonymi" wynikami, które uzyskasz z miękkiego sterty w ramach implementacji, może to spowodować potencjalne przyspieszenie.

Sterty Fibonacciego nie podlegają "korupcji", ale mają czas usunięcia O (log n). Możesz użyć Sterty Fibonacciego jako części ogólnej procedury sortowania, ale ogólną wydajnością twojego sortowania będzie O (n log n).

Answer 2

Aby śledzić na punkcie @ Roba:

Istnieje teoretyczna granica efektywności algorytmów sortujących porównawczych opartych, z których jeden jest sortowanie przez kopcowanie. No comparison-based sort can do have runtime better than Ω(n log n) in the average case. Ponieważ heapsort to Θ (n log n), oznacza to, że jest on asymptotycznie optymalny i nie może być wariantu O (n) średniego czasu (przynajmniej nie opartego na porównaniu). Dowód tego argumentu pochodzi z teorii informacji - bez dokonywania co najmniej porównań Ω (n log n), nie ma możliwości wiarygodnego odróżnienia permutacji wejściowej od żadnej z innych permutacji wejściowych.

Miękki stertę wymyślono, zaczynając od dwumianowej sterty i uszkadzając niektóre ułamki klawiszy, tak że wstawianie i odkładanie n elementów z miękkiego sterty niekoniecznie je sortuje. (The original paper on soft heaps wspomina w swojej abstrakcji, że pomysłowość konstrukcji sztucznie zmniejsza "entropię" zapisanych wartości, aby pokonać barierę Ω (n log n)). Z tego powodu miękki stert może obsługiwać operacje O (1) -time: w przeciwieństwie do zwykłej struktury sterty, nie zawsze sortuje, a zatem nie jest związany przez powyższą barierę środowiska wykonawczego. W związku z tym sam fakt, że n obiektów może zostać zagnieżdżonych i usuniętych z miękkiego sterty w czasie O (n), natychmiast oznacza, że ​​nie można użyć miękkiego sterty, aby przyspieszyć heapsort.

Bardziej ogólnie, nie ma sposobu, aby korzystać żadnego porównania struktury danych opartych zbudować algorytm sortowania chyba zrobić przynajmniej Ω (n log n) pracują średnio po użyciu tej struktury danych. Na przykład: this earlier question wyjaśnia, dlaczego nie można skonwertować sterty binarnej na BST w czasie O (n), ponieważ pozwoliłoby to na sortowanie w czasie O (n) wyłącznie za pomocą porównań (buduj stertę w czasie O (n) , następnie przekonwertuj na BST w czasie O (n), a następnie wykonaj trajektorię inorder w czasie O (n), aby odzyskać posortowaną sekwencję).

Mam nadzieję, że to pomoże!