Transcript Chapter 18 (Heaps)

Fundamentals of Python:
From First Programs Through Data
Structures
Chapter 18
Hierarchical Collections: Trees
An Array Implementation of Binary
Trees
• An array-based implementation of a binary tree is
difficult to define and practical only in some cases
• For complete binary trees, there is an elegant and
efficient array-based representation
– Elements are stored by level
• The array representation of a binary tree is pretty
rare and is used mainly to implement a heap
Fundamentals of Python: From First Programs Through Data Structures
2
An Array Implementation of Binary
Trees (continued)
Fundamentals of Python: From First Programs Through Data Structures
3
An Array Implementation of Binary
Trees (continued)
Fundamentals of Python: From First Programs Through Data Structures
4
An Array Implementation of Binary
Trees (continued)
Fundamentals of Python: From First Programs Through Data Structures
5
Implementing Heaps
Fundamentals of Python: From First Programs Through Data Structures
6
Implementing Heaps (continued)
• At most, log2n comparisons must be made to walk
up the tree from the bottom, so add is O(log n)
• Method may trigger a doubling in the array size
– O(n), but amortized over all additions, it is O(1)
Fundamentals of Python: From First Programs Through Data Structures
7
Using a Heap to Implement a Priority
Queue
• In Ch15, we implemented a priority queue with a
sorted linked list; alternatively, we can use a heap
Fundamentals of Python: From First Programs Through Data Structures
8