Source code online books for professionals by professionals

Hashing, hash tables. Look up a key to get the corresponding value, just like in a search tree. Entries are stored in  
an array, and their positions are found by computing a (pseudorandom, sort of) hash value of the key. Given a good 
hash function and enough room in the array, the expected running time of insertion, deletion and lookup is Q(1).  
(See Chapter 2.)
Heaps, heapsort. Heaps are efficient priority queues. With linear-time preprocessing, a min- (max-) heap will let you 
find the smallest (largest) element in constant time and extract or replace it in logarithmic time. Adding an element 
can also be done in logarithmic time. Conceptually, a heap is a full binary tree where each node is smaller (larger) 
than its children. When modifications are made, this property can be repaired with Q(lg n) operations. In practice, 
heaps are usually implemented using arrays (with nodes encoded as array entries). A very efficient implementation 
can be found in the heapq module. Heapsort is like selection sort, except that the unsorted region is a heap, so finding 
the largest element n times gives a total running time of Q(n lg n). (See the “Black Box” sidebar on heaps, heapq, and 
heapsort in Chapter 6.)