基于图堆的优先级队列实现
Graph-heap-based implementaiton of priority queue
OCaml reference manual提供了一个优先队列实现的例子。
它是基于图形的堆实现。我说 'heap' 是因为每个节点有 0、1 或 2 个子节点，父节点小于或等于其子节点。但是，它不是 'binary heap'，因为插入算法不会强制叶子最左对齐（根据 Wikipedia 定义应该如此），因此树不完整。
我的直觉是这棵树是平衡的，因为每次我们插入一个新节点时：左子树移动到右子树，之前的右子树添加节点并成为新节点左子树。下面的插入会将之前调用的 'new right sub-tree' 移动到左侧并添加节点。
所以左子树的深度与右子树的深度永远不会相差超过1，所以树是平衡的。因此，我们永远不应该以链表形式的树结束，最坏情况下的复杂度应该保持为 O(log n) - 而插入算法要简单得多，因为它不关心保持树的完整（但只平衡）。
我的直觉在这里是正确的吗？我做了一些研究，并没有在其他地方找到这个算法（相反，大多数算法都集中在基于数组的实现上，这显然需要一个完整的树，否则一些槽可能是'invalid'）。
谢谢
您关于堆在插入过程中保持平衡的方式是正确的。
然而，removeMin 操作会扰乱平衡，因为例如，所有左边的元素都可能低于右边的所有元素。没有什么可以恢复余额，所以余额可能会丢失。
因此，如果 N 是堆的大小，则此堆不提供任何 O(log N) 保证。但是，如果 N 是插入的总数，它确实如此，而且还不错。它不会损害大多数使用堆的算法的复杂性。
OCaml reference manual提供了一个优先队列实现的例子。
它是基于图形的堆实现。我说 'heap' 是因为每个节点有 0、1 或 2 个子节点，父节点小于或等于其子节点。但是，它不是 'binary heap'，因为插入算法不会强制叶子最左对齐（根据 Wikipedia 定义应该如此），因此树不完整。
我的直觉是这棵树是平衡的，因为每次我们插入一个新节点时：左子树移动到右子树，之前的右子树添加节点并成为新节点左子树。下面的插入会将之前调用的 'new right sub-tree' 移动到左侧并添加节点。
所以左子树的深度与右子树的深度永远不会相差超过1，所以树是平衡的。因此，我们永远不应该以链表形式的树结束，最坏情况下的复杂度应该保持为 O(log n) - 而插入算法要简单得多，因为它不关心保持树的完整（但只平衡）。
我的直觉在这里是正确的吗？我做了一些研究，并没有在其他地方找到这个算法（相反，大多数算法都集中在基于数组的实现上，这显然需要一个完整的树，否则一些槽可能是'invalid'）。
谢谢
您关于堆在插入过程中保持平衡的方式是正确的。
然而，removeMin 操作会扰乱平衡，因为例如，所有左边的元素都可能低于右边的所有元素。没有什么可以恢复余额，所以余额可能会丢失。
因此，如果 N 是堆的大小，则此堆不提供任何 O(log N) 保证。但是，如果 N 是插入的总数，它确实如此，而且还不错。它不会损害大多数使用堆的算法的复杂性。