Graph-heap-based implementaiton of priority queue

Question

The OCaml reference manual provides an example of priority queue implementation.

It's graph-based implementation of a heap. I said 'heap' because each node has 0, 1 or 2 children and parent node is less than or equals than its children. However, it's not a 'binary heap' as the insertion algorithm doesn't force leaves to be left-most aligned (as it should be according to Wikipedia definition), so the tree isn't complete.

My intuition is that the tree is balanced though, as each time we insert a new node: the left sub-tree moves to the right sub-tree and the previous right sub-tree gets the node added and become new left sub-tree. The following insertion will move the previously called 'new right sub-tree' to the left and gets the node added.

So the depth of the left sub-tree never differs more than 1 from the depth of the right sub-tree, so the tree is balanced. Hence we should never end up in a tree having a linked-list form and worst case complexity should remain O(log n) - while the insertion algorithm is way simpler, as it doesn't take care of keeping the tree complete (but only balanced).

Is my intuition correct here? I make some research and didn't find out this algorithm elsewhere (instead most algorithm focus on array-based implementation, which obviously require a complete tree, otherwise some slots could be 'invalid').

Thanks

Answer 1

You are correct about the way that the heap maintains balance during inserts.

The removeMin operation, however, can disturb the balance, because all the left can be lower than all the elements on the right, for example. There is nothing to restore the balance, and so the balance may be lost.

So this heap does not provide any O(log N) guarantee, if N is the size of the heap. It does, though, if N is the total number of inserts, and that's not too bad. It doesn't hurt the complexity of most algorithms that use heaps.