OCaml图结构堆实现的优先队列平衡性与时间复杂度验证问询

你的直觉完全正确。

• 你提到的这个堆实现属于链式存储的函数式堆，仅满足基础堆序性质（父节点值≤子节点值），不需要满足常规数组式二叉堆要求的完全二叉树结构，所以确实不属于标准定义里的二叉堆范畴。
• 你描述的插入逻辑（每次插入时先把左子树移到右子树的位置，新节点插入原右子树后作为新的左子树），本质是强制插入操作在左右子树之间交替执行，天然保证任意节点的左右子树深度差不会超过1，整棵树的高度始终维持在O(log n)量级，不会出现退化为链表的情况，插入、删除最小元素的最坏时间复杂度都为O(log n)。
• 你检索不到相关资料的原因是这类实现大多仅作为函数式编程的教学演示、模块功能示例出现，没有额外做合并等操作的性能优化，属于极简的小众实现。而主流技术资料里的优先队列大多面向命令式语言的可变场景，会优先选择缓存命中率更高、内存开销更低的数组式完全二叉堆实现，自然很少会提到这类链式实现。
• 如果你有合并多个优先队列的需求，还可以在这个实现的基础上调整为斜堆，能获得*O(log n)*均摊时间复杂度的合并能力，实用性更高。

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