python tree heap implementation

tree_heap.py

from collections import deque
import random


class InvalidOperation(Exception):
    pass


class Node(object):
    def __init__(self, data, left=None, right=None, parent=None):
        self.data = data
        self.left = left
        self.right = right
        self.parent = parent

    def __repr__(self):
        return str(self.data)


class Heap(object):
    """Uses a tree implementation to implement a heap"""
    def __init__(self, root=None):
        self.root = root

    def find_leaf_node(self):
        current = self.root

        if current.left is None and current.right is None:
            return current

        while current.left or current.right:
            if current.left is not None:
                current = current.left
            else:
                current = current.right
        return current

    def add(self, data):
        '''Takes an element and adds it to the heap'''
        if self.root is None:
            # Heap is empty
            self.root = Node(data, None, None, None)
            return self.root

        leaf = self.find_leaf_node()
        # Try making it a sibling
        if leaf.parent is None:
            new_node = Node(data, None, None, leaf)
            leaf.left = new_node
            self.bubble_up(new_node)
        elif leaf.parent.left is None:
            new_node = Node(data, None, None, leaf.parent)
            leaf.parent.left = new_node
            self.bubble_up(new_node)
        elif leaf.parent.right is None:
            new_node = Node(data, None, None, leaf.parent)
            leaf.parent.right = new_node
            self.bubble_up(new_node)
        else:
            # No siblings available, append it left
            new_node = Node(data, None, None, leaf)
            leaf.left = new_node
            self.bubble_up(new_node)
        return

    def bubble_up(self, node):
        '''Bubbles up the node coming in as an argument
        Swaps it with it's parent if need be, then recursively calls itself
        '''
        if node.parent is None:
            # We at root, stop here
            return
        if node.parent.data < node.data:
            # Building a max heap
            node.data, node.parent.data = node.parent.data, node.data
            self.bubble_up(node.parent)
        return

    def bubble_down(self, node):
        '''Bubbles down the node coming in as an argument
        Swap it with its children if needed'''
        if node.right and node.data < node.right.data:
            # Swap them, the parent should have a higher value
            node.data, node.right.data = node.right.data, node.data
            return self.bubble_down(node.right)
        if node.left and node.data < node.left.data:
            # Swap them for the same reason
            node.data, node.left.data = node.left.data, node.data
            return self.bubble_down(node.left)
        return

    def delete_leaf(self, leaf):
        parent = leaf.parent
        if parent is None:
            # We are at root, delete self
            self.root = None
            return
        if parent.right and parent.right.data == leaf.data:
            parent.right = None
            return
        if parent.left and parent.left.data == leaf.data:
            parent.left = None
            return

    def get_max(self):
        if self.root is None:
            return None

        else:
            value = self.root.data
            leaf = self.find_leaf_node()
            self.root.data = leaf.data
            self.delete_leaf(leaf)
            if self.root is not None:
                self.bubble_down(self.root)
            return value

    def __repr__(self):
        '''Performs BFS and prints it out in that order'''
        if self.root is None:
            return ''
        queue = deque([self.root])
        results = []
        while len(queue) > 0:
            current = queue.pop()
            if current is None:
                continue
            else:
                results.append(current.data)
            if current.left is not None:
                queue.appendleft(current.left)
            if current.right is not None:
                queue.appendleft(current.right)

        return '-'.join([str(result) for result in results])


def heapsort(_list):
    h = Heap()
    for elt in _list:
        h.add(elt)

    result = []
    while True:
        temp = h.get_max()
        if temp is None:
            break
        else:
            result.append(temp)
    return result


def main():
    print 'HEAP STUFF'
    h = Heap()
    h.add(10)
    print 'Made basic heap with 1 element, printing it'
    print h

    print '\nAdding a bunch of numbers and printing it again'
    for elt in [3, 7, 5, 2, 8, 10]:
        h.add(elt)

    print h

    print h.get_max()
    print h.get_max()

    print "\n Generating a random list and then sorting it"
    random_ints = [random.randint(0, 1000) for r in xrange(100)]
    print random_ints
    print "\nSorted"
    print heapsort(random_ints)
if __name__ == '__main__':
    main()

This heap is buggy

print heapsort([3, 7, 5, 2, 8, 10])
return [10, 5, 8, 7, 3, 2]