Sortowanie sterty 1-rzędowe?

Question

Jakiś czas temu otrzymaliśmy zadanie napisania programu c, który sortuje tablicę liczb n przy użyciu max-sterty d-ary (sterty, gdzie każdy węzeł ma do d dzieci). Program musiał poprosić użytkownika o wprowadzenie wartości d, wartości między 2 a wielkością tablicy. Podczas sprawdzania mojego programu przypadkowo wpisałem 1 jako wartość d i jakoś algorytm pomyślnie posortował tablicę przy użyciu 1-rzędowej sterty, chociaż zajęło to znacznie więcej czasu niż normalne wartości d.

Jak to możliwe? Stawka 1-rzędowa nie jest nawet stertą, podobnie jak lista, każdy węzeł ma tylko jedno dziecko. Czy ktoś może wyjaśnić, w jaki sposób może się dokonać takie sortowanie?

Answer 1

1-ary kupa jest jeszcze kupa, i spełnia wszystkie niezmienniki, które są wymagane przez sterty sortowania:

• Pierwszym elementem jest największym elementem.
• Perkolacja może przesunąć górny element w dół do prawidłowej pozycji.

W praktyce jednopienny stert jest drzewem, w którym każdy węzeł ma jedno dziecko - jest to również znane jako pojedynczo połączona lista. Ponadto ograniczenie sterty oznacza, że ​​węzeł potomny jest mniejszy niż węzeł nadrzędny. Tak więc, po prostu, 1-helową stertę jest pojedynczo połączoną listą posortowaną w odwrotnej kolejności.

Skonstruowanie sterty na pierwszym miejscu jest równoznaczne z sortowaniem wstawek (wszystkie elementy na liście są umieszczane jeden po drugim). Gdy to zrobisz, usunięcie pierwszego elementu da największy element ze wszystkich, a kolejna perkolacja przeniesie każdy element na liście o jeden poziom wyżej.