# coding=utf-8

# treap(树堆)Python实现

import random

def preorder_tree_walk(node):

    if node:

        print node.key, node.priority

        preorder_tree_walk(node.left)

        preorder_tree_walk(node.right)

def left_rotate(tree, node):

    node_right = node.right

    if not node.p:

        tree.root = node_right

    elif node == node.p.left:

        node.p.left = node_right

    else:

        node.p.right = node_right

    node_right.p = node.p

    node.right = node_right.left

    if node_right.left:

        node_right.left.p = node

    node_right.left = node

    node.p = node_right

def right_rotate(tree, node):

    node_left = node.left

    if not node.p:

        tree.root = node_left

    elif node == node.p.left:

        node.p.left = node_left

    else:

        node.p.right = node_left

    node_left.p = node.p

    node.left = node_left.right

    if node_left.right:

        node_left.right.p = node

    node_left.right = node

    node.p = node_left

class TreapNode(object):

    def __init__(self, key, priority):

        self.key = key

        self.priority = priority

        self.left = None

        self.right = None

        self.p = None

class Treap(object):

    def __init__(self):

        self.root = None

    def find(self, key):

        temp_root = self.root

        while temp_root:

            if key < temp_root.key:

                temp_root = temp_root.left

            elif key > temp_root.key:

                temp_root = temp_root.right

            else:

                return temp_root

        return None

    def insert(self, node):

        temp_root = self.root

        temp_node = None

        while temp_root:

            temp_node = temp_root

            if node.key > temp_node.key:

                temp_root = temp_root.right

            elif node.key < temp_node.key:

                temp_root = temp_root.left

            else:

                raise KeyError, "Error"

        if not temp_node:

            self.root = node

            return

        elif node.key < temp_node.key:

            temp_node.left = node

            node.p = temp_node

        elif node.key > temp_node.key:

            temp_node.right = node

            node.p = temp_node

        self.fixup(temp_node, node)

    def fixup(self, father, child):

        if father:

            if child == father.left and child.priority < father.priority:

                right_rotate(self, father)

            elif child == father.right and child.priority < father.priority:

                left_rotate(self, father)

            self.fixup(father.p, father)

    def delete(self, key):

        node = self.root

        while node:

            if key < node.key:

                node = node.left

            elif key > node.key:

                node = node.right

            else:

                break

        if not node:

            raise KeyError, "Error!"

        flag = 1

        while flag:

            if not node.left:

                if node.right:

                    node.right.p = node.p

                if node.p:

                    if node == node.p.left:

                        node.p.left = node.right

                    else:

                        node.p.right = node.right

                else:

                    self.root = node.right

                flag = 0

            elif not node.right:

                if node.left:

                    node.left.p = node.p

                if node.p:

                    if node == node.p.left:

                        node.p.left = node.left

                    else:

                        node.p.right = node.left

                else:

                    self.root = node.left

                flag = 0

            else:

                # 如果左右子节点均存在 那么把 priority 值大的放到根节点的位置上 网上给的是递归实现 那有没有可能可以递推实现呢？

                # 答案是 有可能的

                if node.left.priority < node.right.priority:

                    right_rotate(self, node)

                else:

                    left_rotate(self, node)

def main():

    number_list = (7, 4, 1, 8, 5, 2, 9, 6, 3)

    tree = Treap()

    for number in number_list:

        priority = random.randint(1, 100)

        node = TreapNode(number, priority)

        tree.insert(node)

    preorder_tree_walk(tree.root)

    print '=========='

    tree.delete(4)

    preorder_tree_walk(tree.root)

if __name__ == '__main__':

    main()