一元堆排序？
不久前，我们接到一项任务，要求编写一个 ac 程序，该程序使用 d 元最大堆（每个节点最多有 d 个子节点的堆）对 n 个数字的数组进行排序。该程序需要要求用户输入 d 的值，一个介于 2 和数组大小之间的值。当我检查程序时，我不小心输入了 1 作为 d 的值，不知何故，该算法成功地使用一元堆对数组进行了正确排序，尽管它比正常的 d 值花费了更多的时间。
这怎么可能？一元堆甚至不是堆，它就像一个列表，每个节点只有一个子节点。谁能解释一下这种排序是如何发生的？
A while back we were given an assignment to write a c program that sorts an array of n numbers using a d-ary max-heap (a heap where each node has up to d children). The program needed to ask the user to input the value of d, a value between 2 and the size of the array. While I was checking my program I accidentally entered 1 as the value of d, and somehow the algorithm succeeded in sorting the array correctly using a 1-ary heap, although it took alot more time than normal values of d.
How is that possible? A 1-ary heap isn't even a heap it's just like a list, every node has only one child. Can anyone explain how this sorting could happen?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
一元堆仍然是堆，并且满足堆排序所需的所有不变量：
实际上，一元堆是一棵树，其中每个节点都有一个子节点 - 这也称为单链表。此外，堆约束意味着子节点小于父节点。所以，简单地说，一元堆是一个按相反顺序排序的单链表。
首先构建堆相当于插入排序（将所有项目逐一渗透到列表中）。完成此操作后，删除第一个元素会产生所有元素中最大的元素，随后的渗透会将列表中的每个项目向上移动一级。
An 1-ary heap is still a heap, and satisfies all the invariants that are required by a heap sort:
In practice, an 1-ary heap is a tree where every node has one child - this is also known as a singly linked list. Also, the heap constraint means the child node is smaller than the parent node. So, simply put, an 1-ary heap is a singly linked list sorted in reverse order.
Constructing the heap in the first place is equivalent to an insertion sort (percolate all items into the list one by one). Once this is done, removing the first element yields the largest element of all, and the subsequent percolation moves every item in the list up by one level.