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

Discussion on Heaps

Understand the structure and implementation of heaps, including binary and randomized meldable heaps. Learn about their efficiency and the decreaseKey operation, which improves performance in graph algorithms. This lesson provides foundational knowledge of heap variants and their applications.

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