A simple binomial tree generator written as a solution to the first Theory Problem in Tim Roughgarden's class Algorithms, Part 1 on Coursera.

binomial_tree.py

import random
import sys
import itertools

# This creates a binomial tree in O(n) time, but using O(n) extra space.
# It's also possible to create an in-place binomial tree in O(n log n) 
# time using O(1) extra space. 

# Each tree here is represented by one leaf and zero or more subtrees
# stored in a list. The leaf is at tree[0]; each following item in the
# list at index `i` is a tree of `2 ** (i - 1)` items.

# Since every tree contains exactly one leaf, there is one tree for
# every value. And since every child tree is linked to every parent tree
# as the result of exactly one call to `binomial_merge`, that function
# is called `n - 1` times. (It's never called for the top-level tree, 
# which is not a child tree.) It does one comparison per turn, and so
# this performs a total of `n - 1` comparisons.

# The resulting top-level tree has a leaf and `log(n)` subtrees. The
# maximum value is contained in the leaf, and the next-to-maximum value is
# in the leaf of one of those subtrees, requiring `log(n) - 1` comparisons
# to find. 

# Note also that when you double the size of the tree, you only double
# the number of child trees, and so the amount of extra space this uses
# is always within a constant factor of n. To be precise, a one-item
# tree requires one pointer (to the value), and any 2n-item tree requires
# twice as many pointers as an n-item tree, plus one. (The extra pointer
# stores the link between the parent tree and its new child.)

# This is based in part on ideas from Tyler Kresch, Slava Irkhin, and
# Xavier Tapon -- thanks!

def binomial_merge(t1, t2):
    if t1[0] >= t2[0]:
        t1.append(t2)
        return t1
    else:
        t2.append(t1)
        return t2

def pairs(seq):
    a = iter(seq)
    return itertools.izip(a, a)

def binomial_tree(seq):
    seq = [[item] for item in seq]
    while len(seq) > 1:
        seq = [binomial_merge(t1, t2) for t1, t2 in pairs(seq)]
    return seq[0]

if __name__ == '__main__':
    p = int(sys.argv[1])
    numbers = random.sample(xrange(2 ** (p + 1)), 2 ** p)

    number_set = set(numbers)
    number_set.remove(max(number_set))

    print "Test using two passes:",
    print max(number_set)
 
    number_tree = binomial_tree(numbers)
 
    print "Using a binomial tree:",
    print max(h[0] for h in number_tree[1:])
    print
    if p > 4:
        print "The first 5 subtrees of the tree:"
        print number_tree[0:5]
    else:
        print "The entire tree:"
        print number_tree