Transcript Oct 30 - Joshua Stough

CSCI 62
Data Structures
Dr. Joshua Stough
October 30, 2008
Today
• Skew heaps  heaps  to implement
priority queue.
•
Heap
• Priority Queue
– PriorityVector – all elements always sorted
• Pros: Convenient, easy to make sense of
• Cons: unnecessary
– Heap – loose ordering, but quickly identify
minimum.
• VectorHeap – for complete heaps. Has improved
performance over PriorityVector, cost more only in
code (not space).
– percolateUp, pushDown
• SkewHeap – BinaryTree to rep general heap.
– merge
HeapSort
• Insert the elements of the input vector
into a VectorHeap:
– Each of n times, add and perform the O(log
n) percolateUp op.
• N times: remove min and place in newly
freed space.
– Each of n times, remove and perform the
O(log n) pushDown op
Skew Heaps
• Heaps are generally not complete
• Vector storage for non-complete heap is
inefficient, use BinaryTree.
– Costs additional reference spaces for each node.
• Need merge for add/remove
– 1. If the left heap has no left child, make the right heap
the left child of the left heap
– 2. Otherwise, exchange the left and right children of the
left heap. Then merge (the newly made) left subheap of
the left heap with the right heap
SkewHeap::merge
Skew Heaps, given merge
On average, as efficient as VectorHeap, with
more storage but no requirement of
contiguous memory.
HeapSortPlay
That’s the end
• What follows are slides for after the
midterm.
Binary Search Trees
• Binary Search Tree: binary tree that is
trivial or if every node > (every value in
left subtree) and <+ (every value in right
subtree).
Binary Search Tree
• Ordered Structure
Binary Search Tree
• More methods
Binary Search Tree
• implementation
Binary Search Tree-locate
(easy idea), lot of code
BST
BST
If value not found,
locate gives node to
add leaf to
containing value,
If locate finds
equivalent, insert
new value as right
child of predecessor
of node returned by
locate.
Predecessor-the
right-most child of
the left subtree
BST
Splay Tree