263 Lecture 2

Priority Queue
Like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it.
An element with high priority is served before an element with low priority.
If two elements have the same priority, they are served according to their order in the queue.
While priority queues are often implemented with heaps, they are conceptually distinct from heaps.
A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Sorted Linked-List
insert(Q, x): O(n)
extractMax(Q): O(1)
max(Q): O(1)
increasePriority(Q, X, K): O(n)
Binary Heap
Binary tree
Nearly complete: Every level is complete except bottom level; bottom level has to be complete from left to right.
Any trees that are nearly complete has log(n)/log(2) child.
Heap Property: Child = 2*index(parent) or 2*index(parent)+1. Parent = floor(child/2)
Max-Heap Insert: Put max insert value to bottom left of tree, then switch value from node until it satisfies max-heap.
max(): O(1)
insert(): O(log(n))
increasePriority(): O(log(n))
extractMax(): O(log(n)). Extract root (Max) 1st & switch w/ left min value to root & switch value w/ its child until max heap property is fully maintained.
Worst runtime case (Convenient to say it is complete): Any level of tree, level has 2^(k-j), j starts from bottom of tree
-At level j of tree, node can be bubbled down j times.
-Max # of bubble down at level j: j * 2^(h-j)
-Total runtime:
∑(j=0, j=h, j*(2^h/2^j))
= (2^n)*n*∑(j=0, j=h, j/(2^j))
≤ n*∑(j=0, j=∞, j/(2^j))
= 2n
Aside: ∑(j=0, j=∞, x^j)
= 1/(1-x) (x<1)
Aside: ∑(j=0, j=∞, j*x^j)
= x/((1-x)^2) (x<1)
Heap sort does not find min value easily.
heapSort(Q): Q <- makeHeap(Q)
While |Q| ≠ 0:
printExtractMax(x): O(n*log(n))
    for i = 1 ...|A|:
        insert(Q, x);