CS240 Lecture Notes - Binary Search Tree, Avl Tree, Radix Sort

216 views1 pages

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.

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents

Related Questions