CS240 Lecture Notes - Binary Search Tree, Avl Tree, Radix Sort
Document Summary
Algorithm: a step-by-step process for carrying out a series of computations. Running time or memory requirement of programs are dependent on hardware, os, and compiler. Heap: is a type of binary tree,stores items with keys,all full, last level to the left, key of parent larger than children(max-heap), height: equal(logn) Advantage storing way: easier to implement, mores space efficiency. Indexes: left( 2*i ), right( 2*i + 1 ) , parent( floor(i/2)) Solution1: start with empty heap & insert one by one & perform bubble up (1ton) worst case time equal(n*logn) Solution2: heapify which bubbles down(n/2 to 1) worst case equal(n) Counting sort: stable , but need to set value {0k} Running time : equal(n+k) when k = o(n) Radix sort: elements with same number of digits(d) Running time: equal(d(n+k)) when k = o(n) and d is constant.