Transcript PPT

CS221: Algorithms and
Data Structures
Lecture #3
Mind Your Priority Queues
Steve Wolfman
2011W2
1
Today’s Outline
• Trees, Briefly
• Priority Queue ADT
• Heaps
– Implementing Priority Queue ADT
– Focus on Create: Heapify
– Brief introduction to d-Heaps
2
Trees
• Family Trees
• Organization Charts
• Classification trees
– what kind of flower is this?
– is this mushroom poisonous?
• File directory structure
– folders, subfolders in Windows
– directories, subdirectories in UNIX
• Function call structure (i.e., a record of everything
3
that goes in the call stack)
Tree Terminology
A
root:
leaf:
child:
parent:
sibling:
ancestor:
descendent:
subtree:
B
D
E
C
F
G
H
J
K
I
L M N
4
Tree Terminology Reference
A
root: the single node with no parent
leaf: a node with no children
B
child: a node pointed to by me
parent: the node that points to me
D E
sibling: another child of my parent
ancestor: my parent or my parent’s ancestor
descendent: my child or my child’s descendent
subtree: a node and its descendents
C
F
H
G
I
J K L M N
We sometimes use degenerate versions
of these definitions that allow NULL as
the empty tree. (This can be very handy for recursive base cases!)
5
More Tree Terminology
depth: # of edges along path from root to node
depth of H?
a. 0
B
b. 1
c. 2
D E
d. 3
e. 4
J
K
A
C
F
G
H
I
L M N
6
More Tree Terminology
height: # of edges along longest path
from node to leaf or, for whole
tree, from root to leaf
height of tree?
a. 0
b. 1
c. 2
d. 3
e. 4
A
B
D
E
C
F
G
H
J
K
I
L M N
7
More Tree Terminology
degree: # of children of a node
degree of B?
a. 0
b. 1
c. 2
d. 3
e. 4
A
B
D
E
C
F
G
H
J
K
I
L M N
8
More Tree Terminology
A
branching factor: maximum degree of
any node in the tree
B
2 for binary trees,
our usual concern;
5 for this weird tree
D
E
C
F
G
H
J
K
I
L M N
9
One More Tree Terminology
Slide
binary: branching factor of 2 (each child has at most 2 children)
A
n-ary: branching factor of n
B
C
D
complete: “packed” binary tree;
as many nodes as
H
possible for its height
E
I
F
G
J
10
nearly complete: complete plus some nodes on the left at the bottom
Tree Calculations
• Find the longest
undirected path in a
tree
• A tree is an empty tree
or a node with some
number of subtrees
• Path might be:
t
–
–
11
Tree Calculations Example
A
B
D
E
C
F
H
J
G
I
K L M N
12
Today’s Outline
• Trees, Briefly
• Priority Queue ADT
• Heaps
– Implementing Priority Queue ADT
– Focus on Create: Heapify
– Brief introduction to d-Heaps
13
Back to Queues
• Some applications
– ordering CPU jobs
– simulating events
– picking the next search site
• Problems?
– short jobs should go first
– earliest (simulated time) events should go first
– most promising sites should be searched first
14
Priority Queue ADT
• Priority Queue operations
–
–
–
–
–
create
destroy
insert
deleteMin
is_empty
G(9) insert
F(7) E(5)
D(100) A(4)
B(6)
deleteMin
C(3)
• Priority Queue property: for two elements in the
queue, x and y, if x has a lower priority value than
y, x will be deleted before y
15
Applications of the Priority Q
•
•
•
•
•
•
•
Call queues for help lines (or don’t you think so?)
Your call will
Hold jobs for a printer in order of length
not be answered
in the order it
Simulate events
was received.
Sort numbers
Store packets on network routers in order of urgency
Select symbols for compression
Anything greedy: an algorithm that makes the “locally best
choice” at each step
16
Naïve Priority Q Data Structures
• Unsorted list:
– insert:
– deleteMin:
• Sorted list:
– insert:
– deleteMin:
a.
b.
c.
d.
e.
O(lg n)
O(n)
O(n lg n)
O(n2)
Something else
17
Today’s Outline
• Trees, Briefly
• Priority Queue ADT
• Heaps
– Implementing Priority Queue ADT
– Focus on Create: Heapify
– Brief introduction to d-Heaps
18
Binary Heap Priority Q Data
Structure
• Heap-order property
Look! Invariants!
– parent’s key is less than or
equal to children’s keys
– result: minimum is always
at the top
2
4
• Structure property
– “nearly complete tree”
– result: depth is always
O(log n); next open location
always known
7
11
5
6
9
10
8
12 14 20
WARNING: this has NO SIMILARITY to the “heap” you hear about
when people say “things you create with new go on the heap”. 19
Nifty Storage Trick
• Calculations:
2
– child:
0
1
2
4
– parent:
5
3
4
7
– root:
6
7
11
– next free:
9
8
6
5
10
8
12 14 20
9
10
0
1
2
3
4
5
6
7
8
2
4
5
7
6
10
8
11
9
9
11
10
11
12
12 14 20
20
DeleteMin
pqueue.deleteMin()
2
2
?
4
7
11
5
6
9
10
12 14 20
4
8
7
11
5
6
9
Invariants violated! DOOOM!!!
10
8
12 14 20
21
Percolate Down
?
4
4
7
5
6
?
10
8
7
11 9 12 14 20
5
6
10
11 9 12 14 20
4
4
6
7
5
?
8
10
11 9 12 14 20
6
8
7
5
12
10
11 9 20 14 20
8
22
Finally…
4
6
7
11
5
12
10
8
9 20 14
23
DeleteMin Code
Object deleteMin() {
assert(!isEmpty());
returnVal = Heap[0];
size--;
newPos =
percolateDown(0,
Heap[size]);
Heap[newPos] =
Heap[size];
return returnVal;
}
int percolateDown(int hole,
Object val) {
while (2*hole + 1 < size) {
left = 2*hole + 1;
right = left + 1;
if (right < size &&
Heap[right] < Heap[left])
target = right;
else
target = left;
if (Heap[target] < val) {
Heap[hole] = Heap[target];
hole = target;
}
else
break;
runtime:
}
return hole;
}
24
DeleteMin Code (Better!)
Do yours this way!!!
Object deleteMin() {
assert(!isEmpty());
returnVal = Heap[0];
size--;
newPos =
percolateDown(0,
Heap[size]);
Heap[newPos] =
Heap[size];
return returnVal;
}
int percolateDown(int hole,
Object val) {
while (numChildren(hole) > 0) {
left = getLeftChild(hole);
right = getRightChild(hole);
if (numChildren(hole) > 1 &&
Heap[right] < Heap[left])
target = right;
else
target = left;
if (Heap[target] < val) {
Heap[hole] = Heap[target];
hole = target;
}
else
break;
runtime:
}
return hole;
}
25
Insert
pqueue.insert(3)
2
2
4
7
11
5
6
9
10
12 14 20
4
8
5
7
11
6
9
10
12 14 20
Invariant violated! What will we do?
8
3
26
Percolate Up
2
2
4
7
5
6
10
4
8
7
11 9 12 14 20 3
5
6
3
11 9 12 14 20 10
2
2
4
7
3
6
8
5
11 9 12 14 20 10
4
8
7
3
6
5
11 9 12 14 20 10 27
8
Insert Code
void insert(Object o) {
assert(!isFull());
size++;
newPos =
percolateUp(size-1,o);
Heap[newPos] = o;
}
int percolateUp(int hole,
Object val) {
while (!isRoot(hole) &&
val < Heap[parent(hole)]
Heap[hole] = Heap[parent(hole)];
hole = parent(hole);
}
return hole;
}
runtime:
28
Note: parent(hole) == (hole-1)/2
Today’s Outline
• Trees, Briefly
• Priority Queue ADT
• Heaps
– Implementing Priority Queue ADT
– Focus on Create: Heapify
– Brief introduction to d-Heaps
29
Closer Look at Creating Heaps
To create a heap given a list of items:
Create an empty heap.
For each item: insert into heap.
Time complexity?
a. O(lg n)
b. O(n)
c. O(n lg n)
d. O(n2)
e. None of these
9, 4, 8, 1, 7, 2
3
5
10
3
12
11
30
A Better BuildHeap
Floyd’s Method. Thank you, Floyd.
12
5
11
3
10
6
9
4
8
1
7
2
pretend it’s a heap and fix the heap-order property!
12
Invariant violated!
Where can the order
invariant be violated
3
in general?
a. Anywhere
b. Non-leaves
4 8
c. Non-roots
5
11
10
1
6
7
2
9
31
Build(this)Heap
12
12
5
11
3
4
10
8
1
2
7
5
9
11
3
6
4
1
2
8 10 7
6
12
12
5
3
4
2
1
8 10 7
6
11
9
1
9
3
4
2
5
8 10 7
6
11
9
32
Finally…
1
3
4
2
5
12 8 10 7
6
9
11
runtime:
33
Build(any)Heap
This is as many violations as we can get.
How do we fix them? Let’s play colouring games!
34
“amortized analysis!”
Today’s Outline
• Trees, Briefly
• Priority Queue ADT
• Heaps
– Implementing Priority Queue ADT
– Focus on Create: Heapify
– Brief introduction to d-Heaps
35
Thinking about Binary Heaps
• Observations
–
–
–
–
–
finding a child/parent index is a multiply/divide by two
operations jump widely through the heap
deleteMins look at all (two) children of some nodes
inserts only care about parents of some nodes
inserts are at least as common as deleteMins
• Realities
– division and multiplication by powers of two are fast
– looking at one new piece of data sucks in a cache line
– with huge data sets, disk accesses dominate
BUT… don’t solve a performance
36
problem until you know you have one!
Solution: d-Heaps
• Nodes have (up to) d children
• Still representable by array
• Good choices for d:
1
3
7
2
– optimize (non-asymptotic)
4 8 5 12 11 10 6 9
performance based on
ratio of inserts/removes
1 3 7 2 4 8 5 12 11 10 6 9
– make d a power of two
for efficiency
– fit one set of children in a cache line
d-heap mnemonic:
– fit one set of children on a memory
37
d is for degree!
page/disk block
To Do
• Read: KW Section 8.5
• Keep working on homework!
• Start preparing for the exam… it’s not that far
away!
38
Coming Up
• Sorting, sorting, and more sorting!
• Midterm (Wed Feb 15, 5-7PM, loc’n TBD)
39