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 containing 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 ...