class Node:
    def __init__(self, value=None):
        # 記得class的特性, 每一個Node, 皆要去實現這4個 屬性的components.
        self.value = value
        self.left = None
        self.right = None
        self.parent = None

    def __repr__(self):
        # Helpful method to keep track of Node values.
        return "<Node: {}>".format(self.value)

class MaxHeap:
    def __init__(self):
        self.root = None

    # Implement your `insert` method here.

    def insert(self, value):
        # create a node for when calling the insert method
        node = Node(value=value)
        # if root of the MaxHeap tree is not existed, set the firstly insert node as root.
        # case 1: the root is not existed, have to set the new insert node to the root.
        if not self.root:
            self.root = node
            return node
        # if the root existed, compare the value of the root node with the inserted node.
        # case 2: the root existed, and the root value >= inserted value ======> is the normal insert.
        if self.root.value >= node.value:
            # Normal insert.
            node.parent = self.root
            if not self.root.left:
                self.root.left = node
            elif not self.root.right:
                self.root.right = node
            # remember for each
            return node


        # case 3: the root existed, and the root value < inserted value =======> is the swap insert.
        # Swap the nodes.

        old_root = self.root
        node.left = old_root.left
        node.right = old_root.right
        self.root = node

        if not self.root.left:
            self.root.left = old_root
        elif not self.root.right:
            self.root.right = old_root
        return node

if __name__=="__main__":
    heap = MaxHeap()
    heap.insert(3)
    heap.insert(9)
    heap.insert(11)
    root = heap.root.value
    left = heap.root.left.value
    right = heap.root.right.value