1-ary堆排序？

Question

回過頭來，我們被賦予了寫一個c程序的任務，該程序使用d-ary最大堆（每個節點最多有d個孩子的堆）對n個數字排序。該程序需要用戶輸入d的值，該值是2和數組大小之間的值。當我檢查程序時，我意外地輸入了1作爲d的值，並且不知何故該算法成功地使用1堆堆正確地對數組進行排序，儘管它比d的正常值花費了更多時間。

這怎麼可能？ 1-ary堆甚至不是堆，就像列表一樣，每個節點只有一個孩子。任何人都可以解釋這種排序如何發生？

Answer 1

的1進制堆仍然是一個堆，並且滿足所有由一個堆排序所需的不變量：

• 第一個元素是最大的元素。
• 滲濾可將頂部元件向下移動到其正確位置。

實際上，1元堆是一棵樹，每個節點都有一個孩子 - 這也被稱爲單向鏈表。此外，堆約束意味着子節點小於父節點。所以，簡單地說，1元堆是按相反順序排列的單鏈表。

首先構建堆相當於插入排序（逐個將所有項滲透到列表中）。完成此操作後，移除第一個元素將生成所有元素的最大元素，隨後的滲濾將列表中的每個項目移動一個級別。