The Cheriton-Tarjan MST algorithm finds MSTs in time O(m log log n) in arbitrary graphs by using a cleverly-modified version of a leftist heap data structure to store edges. It was developed in 1976. The algorithm relies on the fact that leftist heaps can be merged in time O(log n), but also uses the fact that leftist heaps are binary trees and therefore that every node has at most two children.
In 1978, binomial heaps were invented as a cleaner type of heap that supports merging in O(log n) time. Since then, most algorithms that need mergable heaps either use binomial heaps or some other related structure. However, since binomial heaps don't use binary trees, the Cheriton-Tarjan algorithm's main optimization (namely, eliminating unnecessary edges by doing a top-down DFS over the heap) won't work in the same time bounds when run on a binomial heap rather than a leftist heap.
Has there been any work done to update the Cheriton-Tarjan MST algorithm to use binomial heaps rather than leftist heaps?
Thanks!