Instantly share code, notes, and snippets.

# braddunbar/heap.py Created Oct 1, 2009

What would you like to do?
class
 # maxheap def maxheapify(a,i): while i < len(a): l,r = 2*i+1,2*i+2 m = i if l < len(a) and a[l] > a[i]: m = l if r < len(a) and a[r] > a[m]: m = r if m == i: break t = a[i] a[i] = a[m] a[m] = t i = m def buildheap(a): for i in reversed(range(len(a) // 2)): maxheapify(a,i) def popmax(a): mx = a[0] a[0] = a[-1] a.pop() maxheapify(a,0) return mx if __name__ == '__main__': a = [27,17,3,16,13,10,1,5,7,12,4,8,9,0] print(a) maxheapify(a,2) print(a) a = [4,1,3,2,16,9,10,14,8,7] print(a) buildheap(a) print(a) popmax(a) print(a)
 import operator from functools import reduce def prod(seq): return reduce(operator.mul, seq, 1) def memoize(f): d = {} def mem(*args): if not args in d: d[args] = f(*args) return d[args] return mem def chain(ps): @memoize def __chain__(ps): if len(ps) == 3: return prod(ps) def val(k): return __chain__(ps[:k]+ps[k+1:]) + prod(ps[k-1:k+2]) return min(map(val, range(1,len(ps)-1))) return __chain__(ps) def lcs(x,y): @memoize def __lcs__(a,b): if not a or not b: return 0 if x[a-1] == y[b-1]: return __lcs__(a-1,b-1) + 1 return max(__lcs__(a-1,b), __lcs__(a,b-1)) return __lcs__(len(x),len(y)) if __name__ == '__main__': print(lcs('brad', 'dunbar')) #2 print(lcs('abcxyzabc', 'xyzabcxyz')) #6 print(chain((10,30,5,60))) #4500