1-ary堆排序？

Question

1-ary堆排序？

6

不久前，我们被分配编写一个C程序，使用d叉最大堆（每个节点最多有d个子节点）对n个数字的数组进行排序。程序需要要求用户输入d的值，该值介于2和数组大小之间。当我检查我的程序时，我不小心将d的值输入为1，但一些方式下，算法成功地使用1叉堆正确地对数组进行了排序，尽管它花费了比正常d值更多的时间。

这怎么可能呢？1叉堆甚至不是堆，只是像列表一样，每个节点只有一个子节点。有人能解释这种排序是如何发生的吗？

- Bob

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Victor Nicollet · Accepted Answer

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

第一个元素是最大的元素。
过滤可以将顶部元素移动到其正确的位置。

在实践中，一个一元堆是一棵树，每个节点都有一个孩子 - 这也被称为单链表。此外，堆约束意味着子节点小于父节点。因此，简而言之，一个一元堆是按相反顺序排序的单链表。首先构建堆等同于插入排序（逐个将所有项目过滤到列表中）。完成后，删除第一个元素会产生所有元素中最大的元素，并且随后的过滤会将列表中的每个项目上移一个级别。