# 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]
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
``````