algorithm - 一元堆排序？

Question

不久前，我们被分配编写 ac 程序，该程序使用 d-ary max-heap（每个节点最多有 d 个子节点的堆）对包含 n 个数字的数组进行排序。程序需要要求用户输入 d 的值，一个介于 2 和数组大小之间的值。当我检查我的程序时，我不小心输入了 1 作为 d 的值，并且不知何故，该算法成功地使用一元堆正确地对数组进行了排序，尽管它比 d 的正常值花费了更多的时间。

这怎么可能？一元堆甚至不是堆，它就像一个列表，每个节点只有一个孩子。谁能解释这种排序是如何发生的？

Answer 1

一元堆仍然是堆，并且满足堆排序所需的所有不变量：

• 第一个元素是最大的元素。
• 渗透可以将顶部元素向下移动到正确的位置。

在实践中，一元堆是一棵树，其中每个节点都有一个孩子——这也称为单链表。此外，堆约束意味着子节点小于父节点。因此，简单地说，一元堆是一个以相反顺序排序的单链表。

首先构造堆相当于插入排序（将所有项目逐个渗透到列表中）。完成此操作后，删除第一个元素会产生所有元素中最大的元素，随后的渗透将列表中的每个项目上移一级。