Search⌘ K
Home
Courses
Data Structures with Generic Types in Java

Discussion on Heaps

Discover how heaps are represented and used in Java, focusing on BinaryHeap, MeldableHeap, and other variants. Learn their operational efficiencies and applications like priority queues and graph algorithm optimization.

We'll cover the following...

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