CSC 263 Lecture Summary for Week 2 Fall 2019
READINGS: Chapter 6.
SELFTEST: Exercises 6.11, 6.14, 6.24.
Volunteer note takers
Helps your fellow classmates
Improves your own note taking
May be noted on your co curricular record
Expectations
Material from last week, including the problem set, is review Ch.15
Do the readings before class
For problem sets: listen to instructions given in class
Treat problem sets as testing your own understanding
Most questions from piazza were answered in class
InstructorsTAs will post less and less on piazza
Its not a place to get feedback from instructors
You will implement and augment a lot of ADTs
If we dont specify a behaviour that means its up to you
Justify your choices that may mean doing some research
I described precisely, in English,
the data structure wed use for stacks
of computational units for a line is an arbitrary constant;
No effect on the theta bound
Priority Queues
Priority queue: like a queue except every item has a priority usually a
number that determines retrieval order. More formally, a priority queue
consists of a set of elements S, where each element has a priority.
Operations:
INSERTS,x: insert x in the set priority of x stored in x.priority
MAXIMUMS: return element from S with largest priority
EXTRACTMAXS: remove and return element from S with largest priority
INCREASEPRIORITYS,x,k: increase priority of x to value k
x must already belong to S
Applications:
job scheduling in an operating system
printer queues
eventdriven simulation algorithms
etc.
Data structures:
Unsorted list? Thetan for EXTRACTMAX.
Sorted list by priorities? Thetan for INSERT.
Special case:
If only a fixed number k of priorities p1,p2,…,pk and k is small,
then keep an array with k positions one for each priority and store
items in a linked list at each position.
INSERT takes time Theta1.
MAXIMUM, EXTRACTMAX require time Thetak.
INCREASEPRIORITY takes time Theta1.
Heaps
Simple data structure used to represent priority queues. Stores items in
complete binary trees each level contains maximum number of nodes, except
possibly last level, and nodes in last level as far left as possible, and
in heap order: every node has priority greater than or equal to priorities
of its immediate children. Implication: every subtree of a heap is also a
heap.
Example: 17 Complete tree: ensures height is small.
Heap order: supports faster heap operations.
9 12 Intuition: tree is partially sorted. Enough to
make query operations fast while not requiring
7 7 9 5 full sorting after each update.
3 4
Trick: rather than use nodes references pointers, heap elements stored in
array together with integer heapsize. Conventions: root at index 1; children
of root at indices 2, 3; grandchildren of root at indices 4, 5, 6, 7; etc.
Using index 1 for root simplifies calculations: children of node at index i
are 2i left and 2i1 right; parent of node at index i is floori2.
Navigating paths done with simplest of binary arithmetic operations!
Example: heap above stored as 17,9,12,7,7,9,5,3,4.
Operations.
INSERT: Increment heapsize, add element at new index heapsize.
Result might violate heap property: percolate element up exchange it
with its parent until priority no greater than priority of parent.
Example: INSERT13 on previous heap.
17 17
9 12 9 12
7 7 9 5 7 13 9 5
3 4 13 3 4 7
17,9,12,7,7,9,5,3,4,13 17,9,12,7,13,9,5,3,4,7
17
13 12
7 9 9 5
3 4 7
17,13,12,7,9,9,5,3,4,7
Running time? Thetaheight Thetalog n.
MAXIMUM: Return element at index 1 if heapsize 1. Theta1 time.
EXTRACTMAX: Decrement heapsize, remove element at index 1. This leaves
hole at index 1: move element at index heapsize1 into index 1.
Restore heap order by percolating down exchange with highest priority
child until priority is greater than or equal to both children, or leaf is
reached.
Example: EXTRACTMAX on previous heap.
7
13 12 13 12
7 9 9 5 7 9 9 5
3 4 7 3 4
,13,12,7,9,9,5,3,4,7 7,13,12,7,9,9,5,3,4
13 13
7 12 9 12
7 9 9 5 7 7 9 5
3 4 3 4
13,7,12,7,9,9,5,3,4 13,9,12,7,7,9,5,3,4
Running time? Thetalog n.
INCREASEPRIORITY: simply percolate element up the heap to restore head
order.
Example: INCREASEPRIORITY4,10
13 13
9 12 9 12
7 7 9 5 10 7 9 5
3 10 3 7
13,9,12,7,7,9,5,3,10 13,9,12,10,7,9,5,3,7
13
10 12
9 7 9 5
3 7
13,10,12,9,7,9,5,3,7
Running time? Thetalog n.
HeapSort: unlike binary search trees, heaps do not maintain complete ordering
of elements. Nevertheless, heaps have other uses besides implementing
priority queues in particular, sorting.
Observation: heap root stores maximum element.
Idea: swap root with last element; now last element is in sorted position,
so decrement heapsize, restore heap order, and repeat.
Runtime? Each phase is Thetalog n, there are n phases, and at least n2
elements require Omegalog n 1: total Thetan log n.
Missing? Arbitrary input array not necessarily in heap order.
Heapify: create heap from unsorted array A.
Idea 1:
B empty array of size A.length
for x in A:
B.insertx heap insertion
Runtime? Thetan log n: Olog n for each insertion, and in
worstcase, Omegalog n 1 for at least n2 elements.
Idea 2:
for i n2,…,1,0:
A.percolatedowni
Advantage? Inplace no need for second array.
Runtime? On log n as before. But not Omegan log n! More careful
analysis:
n2 elements require at most 0 swap
n4 elements require at most 1 swap
n8 elements require at most 2 swaps
…
1 element requires at most log n swaps
Total sumi1,…,log n i n2i1
n2 sumi1,…,log n i2i
n2 sumi1,…,oo i2i
n2 2