1-ary堆排序？

Question

不久前,我们得到了一个编写ac程序的赋值,该程序使用d-ary max-heap(每个节点最多有d个子节点的堆)对n个数字的数组进行排序.程序需要让用户输入d的值,一个介于2和数组大小之间的值.当我检查我的程序时,我偶然输入1作为d的值,并且不知何故算法成功地使用1-ary堆正确地对数组进行排序,尽管它比d的正常值花费了更多的时间.

怎么可能？1-ary堆甚至不是堆,它就像列表一样,每个节点只有一个子节点.任何人都可以解释这种排序是如何发生的

Answer 1

1-ary堆仍然是堆,并且满足堆排序所需的所有不变量:

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

实际上,1-ary堆是一棵树,每个节点都有一个子节点 - 这也称为单链表.此外,堆约束意味着子节点小于父节点.因此,简单地说,1-ary堆是以相反顺序排序的单链表.

首先构造堆等同于插入排序(将所有项逐个渗透到列表中).完成此操作后,删除第一个元素将产生所有元素中的最大元素,随后的渗透会将列表中的每个项目向上移动一个级别.