Transcript CSC 2500 Computer Organization

CSC 2300
Data Structures & Algorithms
March 13, 2007
Chapter 6. Priority Queues
Today – Priority Queues






Priority queues
Array representation of binary heaps
Binary heap operations – insert and deleteMin
Build heap operation
Why buildHeap takes linear time?
Brief review – binary search tree, AVL tree, splay
tree, heap
Binary Heaps
Array Implementation
Example – Insert 14
Example – deleteMin
deleteMin
percolateDown
Time Behavior



What is the worst-case time for deleteMin?
What is the worst-case time for insert?
What is the average-case time for insert?
Examples in Class

We may illustrate the idea with a few examples:
http://window.terratron.com/~sosman/computers/java/heap/
Build Heap

How much time is required?
buildHeap
Example

percolateDown(7):
Example

percolateDown(6) and then percolateDown(5):
Example

percolateDown(4) and then percolateDown(3):
Example

percolateDown(2) and then percolateDown(1):
buildHeap








We start with an unordered tree.
The seven remaining trees show the result of each of the seven percolateDowns.
Each dash line corresponds to two comparisons: one to find the smaller child and
one to compare the smaller child with the node.
Note that there are only 10 dashed lines in the entire algorithm (there could have
been an 11th – where?) corresponding to 20 comparisons.
How do we bound the running time of buildHeap?
How do we bound the number of dashed lines?
Why do we compute the sum of the heights of all the nodes?
What is an upper bound for the sum?
Theorem 6.1







For the perfect binary tree of height h containing 2h+1 – 1 nodes,
the sum of the heights of the nodes is 2h+1 – 1 – (h+1).
It is easy to see that this tree consists of one node at height h,
two nodes at height h – 1, 22 nodes at height h – 2, and in
general 2i nodes at height h – i.
The sum of the heights of all the nodes is therefore
S = h + 2(h – 1) + 22(h – 2) + 23(h – 3) + … + 2h–1 (1)
How do we find S?
Multiply equation by 2:
2S = 2h + 22(h – 1) + 23(h – 2) + 24(h – 3) + … + 2h (1)
Subtract and get
S = –h + 2 + 22 + 23 + … + 2h–1 + 2h
What does S equal?
Exact Value of S







Sum of the heights equals N – b(N), where b(N) is the number of 1’s
in the binary representation of N.
We may prove this result by induction.
An illustration:
N = 10, or 1010 in binary. Sum of height = 10 – 2 = 8.
Add one node. N = 11, or 1011 in binary. Sum of height = 11 – 3 = 8.
Add one node. N = 12, or 1100 in binary. Sum of height = 12 – 2 = 10.
Add one node. N = 13, or 1101 in binary. Sum of height = 13 – 3 = 10.
Binary Search Tree







Property that turns a binary tree into a binary search tree
Which is the appropriate node traversal scheme?
Operation contains
Operation findMin
Operation findMax
Operation insert
Operation remove
AVL Tree

Property that turns a binary search tree into an AVL tree
Balance condition
Single rotation
Double rotation

Operations contains, findMin, findMax, insert, remove. Time?



Splay Tree




Is it a binary search tree?
What does a splay tree guarantee?
Basic idea of splay tree?
Zig-zig and zig-zag:
Heap




Is it a binary search tree?
What is a complete binary tree?
Operations insert, deleteMin, and buildHeap.
Operations percolateUp and percolateDown.