wiki

wiki is ...

code for 3-12

f = open("yob1995.txt","r")
maxname = "none"
maxval = 0
max2name = "none"
max2val = 0

for line in f:
    (name, sex, count) = line.rsplit(",")
    count = int(count)

    if sex == "F":
        if count > maxval:
            max2name = maxname
            max2val = maxval
            maxval = count
            maxname = name
        elif count > max2val:
            max2name = name
            max2val = count

print maxname, max2name
print maxval, max2val

code for 3-15

def rank(L, v):
    pos = 0
    for val in L:
        if val < v:  pos += 1
    return pos

partition code

def partition(L,v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return smaller + [v] + bigger

## partiction code modified with top K
def partition(L,v):
    smaller = []
    bigger = []
    for val in L:
        if val < v: smaller += [val]
        if val > v: bigger += [val]
    return (smaller, [v], bigger)

def top_k(L,k): 
    v = L[random.randrange(len(L))]
    (left,middle,right) = partition(L,v)
    if len(left) == k: return left
    if len(left)+1 == k: return left+[v]
    if len(left) > k: return top_k(left,k)
    return left+[v]+top_k(right,k-len(left)-1)

def left(i): return i*2+1
def right(i): return i*2+2
def parent(i): return (i-1)/2
def root(i): return i==0
def leaf(L,i): return right(i) >= len(L) and left(i) >= len(L)
def one_child(L,i): return right(i) == len(L)

def down_heapify(L,i):
    # If i is a leaf, heap property holds
    if leaf(L,i): return 
    # if i has one child ...
    if one_child(L,i):
        # check heap property
        if L[i] > L[left(i)]:
            # if it fails, swap, fixing i and its child (a leaf)
            (L[i], L[left(i)]) = (L[left(i)], L[i]])
        return
    # if i has two children ... 
    # check heap property
    if min(L[left(i)], L[right(i)]) >= L[i]: return 
    # if it fails, see which child is the smaller
    # and swap i's value into that child
    # afterwards, recurse into that child, which might violate
    if L[left(i)] < L[right(i)]:
        # Swap into left child
        (L[i], L[left(i)]) = (L[left(i)],L[i])
        down_heapify(L,left(i))
        return 
    (L[i], L[right(i)]) = (L[right(i)], L[i])
    down_heapify(L,right[i])
    return