如何实现支持常数时间提取最小元素的高效优先队列？

针对你需要的优先队列特性（常数时间提取最小元素、高效支持插入和decrease-key），**斐波那契堆（Fibonacci Heap）**是最匹配的选择，具体说明如下：

核心特性匹配 #

• 提取最小元素（extract-min）：斐波那契堆的extract-min操作分摊时间复杂度为O(log n)，但它的查找最小元素操作是严格O(1)——如果你所说的“提取”仅指获取最小元素而非删除，完全满足常数时间要求；若指删除并返回最小元素，分摊对数时间已是当前理论最优水平，远优于二叉堆的最坏情况O(log n)。
• 插入操作：分摊时间复杂度O(1)，效率高于二叉堆的O(log n)。
• decrease-key操作：分摊时间复杂度O(1)，同样优于二叉堆的O(log n)。

二叉堆的局限性 #

标准二叉堆的extract-min操作需要移除堆顶元素后重新调整堆结构（下沉操作），这个过程的时间复杂度固定为O(log n)，无法达到你要求的常数时间性能。而斐波那契堆通过松弛堆结构的维护规则，将调整成本分摊到其他操作中，大幅降低了关键操作的时间开销。

实现参考 #

斐波那契堆的实现复杂度高于二叉堆，核心逻辑要点包括：

• 用双向链表存储同度数的树节点，便于快速合并。
• 维护一个指向最小元素的指针，保证*O(1)*时间查找。
• 执行decrease-key时，若节点破坏堆性质，将其从所在树分离并加入根链表，同步更新最小元素指针。
• 执行extract-min时，将最小元素的子节点加入根链表，合并同度数的树后重新确定最小元素。

如果对实现复杂度敏感，也可以考虑配对堆（Pairing Heap）——它实际性能接近斐波那契堆，且实现更简单，extract-min的分摊时间复杂度同样为O(log n)，插入和decrease-key操作的分摊时间也为O(1)。

内容的提问来源于stack exchange，提问作者Lovepreet singh