Search⌘ K
AI Features
Home
Courses
Data Structures with Generic Types in C++

Discussion on Heaps

Explore how heaps, including binary heaps and randomized meldable heaps, are represented and implemented. Learn about their variations, key operations like remove and decreaseKey, and their impact on algorithms such as Dijkstra's shortest path. Understand the historical context and efficiency of these data structures to improve your C++ programming skills.

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