Thanks for your comments!

I'm sorry to say I don't know any more about building heaps faster than the little bit I said in the article. I got what I wrote about Tarjan's algorithm from the Wikipedia article, Heap (data structure), but I haven't looked into it myself at all. Sorry I can't be more help.