Transcript PowerPoint

Priority Queues
What is a Priority Queue?
•
Container of elements where each
element has an associated key
A key is an attribute that can identify rank
or weight of an element
•
•
Examples – passenger, todo list
Priority Queue ADT Operations
•
•
•
•
•
•
size()
isEmpty()
insertItem(k, e) – insert element e with key k
minElement() – return ref to min element
minKey() – return const ref to smallest key
removeMin() – remove and return element with
smallest key
Example
•
•
•
•
•
•
•
insertItem(5, A)
insertItem(9, C)
insertItem(3, B)
insertItem(7, D)
minElement()
minKey()
removeMin()
•
•
•
•
•
•
•
size()
minElement()
removeMin()
removeMin()
removeMin()
removeMin()
isEmpty()
The Comparator Pattern
• Suppose we want a priority queue of
“Appointment” objects
• How do we determine that one
appointment is before another?
• Need to compare Appointment objects
– operator overloading versus standard function
Implementation
• Using an array?
• Using a linked list?
• Running time of insertItem/removeMin?
Sorting
• Can you sort a list of numbers using a
priority queue?
• Algorithm?
Heaps
• A heap is a priority queue implemented
with a binary tree
Heaps
• Heap-Order Property: In a heap T, for
every node v other than the root, the key
stored at v is greater than or equal to the
key stored at v’s parent
Heaps
• Complete Binary Tree Property: A heap T
with height h is a complete binary tree,
that is, levels 0,1,2,…,h-1of T have the
maximum number of nodes possible and
all the internal nodes are to the left of the
external nodes in level h-1.
• What does this give us?
Example Heap
root
4
9
7
15
11
56
10
Heap Implementation
• Insertion algorithm
new_node
5
root
4
9
7
15
11
56
10
Up-Heap Bubbling
while new node is smaller than its parent
swap parent and node
• Running time?
Heap Implementation
• Deletion algorithm
delete 4
root
4
9
5
7
15
11
56
10
Down-Heap Bubbling
if right child is null
if left child is smaller than current
swap left and current
if both children not null
swap current with smallest child
Vector Implementation
0
1
2
3 4
5
6
7
• Children are positions index*2 and
index*2+1
• Implementation of insert and remove?
Heap Sort
• Algorithm to use a heap to sort a list of
numbers
• Running time?