#!/usr/bin/python

#max heap

import ahnentafel

def push(data, tree=None):
	if tree:
		index = len(tree)
		tree.append(data)
		parent = ahnentafel.parent(index)
		while (tree[index] > tree[parent]) and (index > 0):
			tree[index], tree[parent] = tree[parent], tree[index]
			index = parent
			parent = ahnentafel.parent(index)
		return tree
	else:
		return [data]

def pop(tree):
	if tree:
		index = 0
		out = tree[0]
		tree[0] = tree[-1]
		tree.pop()
		last = len(tree)
		while (index < last):
			left = ahnentafel.left(index)
			right = ahnentafel.right(index)
			if (left < last) and (tree[left] > tree[index]):
				largest = left
			else:
				largest = index
			if (right < last) and (tree[right] > tree[largest]):
				largest = right
			if largest != index:
				tree[index], tree[largest] = tree[largest], tree[index]
				index = largest
			else:
				break
		return out
	else:
		return None

def merge(other, tree=None):
	while other:
		tree = push(other.pop(), tree)
	return tree


if __name__ == "__main__":
	import random
	l = push(1)
	tmp = range(10)
	for i in range(6):
		push(random.randint(2,10), l)
	print l
	print pop(l)
	print l