algorithm - 以最类似于基于 PQ 的排序方式进行的算法

因此，我试图找出以与以下结构的基于 PQ 的排序最相似的方式进行的算法。

举个 heapsort 和 d-heaps 的例子。Heapsort 使用 2-heap 作为中间表示来对内容进行排序。对于堆排序，尽管任何 PQ 都可以工作，但 PQ 是 2 堆。

标签： algorithmheappriority-queue

我不确定你所说的 1 堆是什么意思。使用标准术语，1 堆将是一个每个节点有一个子节点的堆：链表。那不会表现得很好。

3 堆只是d = 3的d堆。你说堆排序使用2堆。这并不总是正确的。许多人使用 2 堆实现堆排序，通常是因为他们不知道可以使用 3 堆。这是不幸的，因为 3 堆在许多情况下可能更有效。我和许多其他人已经使用 3 堆实现了堆排序。

如果“n-1 堆”是指具有 n-1 个根子节点的堆，那效率不会很高。对于根的 n-1 个孩子，当您删除最小的项目时，您必须搜索所有 n-1 个孩子以找到新的根。您不妨重复地在线性列表中搜索下一个最大的项目。“n-1”堆排序将具有与选择排序相同的性能。

平衡的二叉搜索树将比不平衡的二叉搜索树执行得更好，但构建树的成本很高。堆排序的美妙之处在于您可以在 O(n) 中就地构建堆。构建 BST 是 O(n log n)。尽管删除最小节点对两者来说都是 O(log n) 操作，但现实世界的性能有利于堆。

综上所述，任何可以用作优先级队列的数据结构都可以用于基于 pq 的排序。二进制堆（更普遍地，d - ary heap）是常用的，因为它易于实现且非常高效。但是，根据您的应用程序，诸如配对堆之类的东西可能会胜过二叉堆。