Additional notes
The implicit representation of a complete binary tree as an array, or list, seems to have been first proposed by EytzingerM. Eytzinger. Thesaurus principum hac aetate in Europa viventium (Cologne). 1590. In commentaries, ‘Eytzinger’ may appear in variant forms, including: Aitsingeri, Aitsingero, Aitsingerum, Eyzingern.. He used this representation in books that contained pedigree family trees of noble families. The BinaryHeap data structure described here was first introduced by WilliamsJ. Williams. Algorithm 232: Heapsort. Communications of the ACM, 7(6):347–348, 1964..
The randomized MeldableHeap data structure described here appears to have first been proposed by Gambin and MalinowskiA. Gambin and A. Malinowski. Randomized meldable priority queues. In SOFSEM98: Theory and Practice of Informatics, pages 344– 349. Springer, 1998.. Other meldable heap implementationsC. Crane. Linear lists and priority queues as balanced binary trees. Technical Report STAN-CS-72-259, Computer Science Department, Stanford University, 1972. exist, including leftist heapsD. Knuth. Sorting and Searching, volume 3 of The Art of Computer Programming. Addison-Wesley, second edition, 1997., binomial heapsJ. Vuillemin. A data structure for manipulating priority queues. Communications of the ACM, 21(4):309–315, 1978., Fibonacci heapsM. Fredman and R. Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. Journal of the ACM, 34(3):596–615, 1987., pairing heapsM. Fredman, R. Sedgewick, D. Sleator, and R. Tarjan. The pairing heap: A new form of self-adjusting heap. Algorithmica, 1(1):111– 129, 1986., and skew heapsD. Sleator and R. Tarjan. Self-adjusting binary trees. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25–27 April, 1983, Boston, Massachusetts, USA, pages 235–245. ACM, ACM, 1983., although none of these are as simple as the MeldableHeap structure.