CMPSC 130A Lecture Notes - Lecture 4: Linked List, Time Complexity, Data Structure
Document Summary
** there are approximately n/2 nodes at the leaf level of a heap of n elements. = + 2( 1) + 4( 2) + + 2,-. 2 = 2 + 4( 1) + 8( 2) + 2, 12 ( + 1) () Depending on type of members and choice of operations, different implementations can have different asymptotic complexity. Data structure with 3 basic operations: find (i): find item with key i insert (i): insert i into the dictionary remove (i): delete i. The keys to be managed come from a known but very large set, called universe u. Non-numeric keys (strings, webpages) are converted to numbers. Sum of ascii values, first three characters, etc. The set of keys to be managed is s, a subset of u. The size of s is much smaller than u, namely, |s| << |u| You can maintain a linked list of key entries instead of storing a single key in an index.
