文档介绍：算法和数据结构11
Outline of Lecture
ADT Priority Queue
Linear List Representation
Heap Data Structure (better alternativen Min-Heap:
Every node stores a value that is less then or equal to that of its children
Root stores minimum of all values in tree
2019-3
7
Min Priority Queue
Collection of elements.
Each element has a priority or key.
Supports following operations:
isEmpty
size
add/put an element into the priority queue
get element with min priority
remove element with min priority
2019-3
8
Max Priority Queue
Collection of elements.
Each element has a priority or key.
Supports following operations:
isEmpty
size
add/put an element into the priority queue
get element with max priority
remove element with max priority
2019-3
9
Summary and Analysis
Determine the structure of the new heap first
Must satisfy complete binary tree principle
Move up the tree, swapping nodes as necessary
Single pass from newly inserted leaf towards root
Analysis:
At each level, spent constant amount of time: (1)
Number of levels is h running time bounded by O(h) or O(logn)
2019-3
15
Deletion from Max Heap
15
20
14
10
2
21
20
15
2
14
10
15
2
14
10
20
15
14
2
10
2019-3
16
Summary and Analysis
Remove root element only
Must maintain complete binary tree structure
Single pass from root towards a leaf, filling the hole with the larger of the two children
Following the gap down the tree until we reach leaf
Analysis:
At each level, spent constant amount of time: (1)
Number of levels is h running time bounded by O(h) or O(logn)
2019-3
17
Initialization of Max Heap
Assume n elements; two options
(1) n calls to insert, resulting in O(nlogn) running time
(2) special initialization strategy, (n) running time
Assume all n elements are available at the beginning of initialization process
Sequence of exchanges of elements to build up heap
2019-3
18
Initial Scenario
Array a of n element