## 实现

class Card:
def __init__(self, title, priority):
self.title = title
self.priority = priority

def __gt__(self, b):
return self.priority > b.priority

def __str__(self):
return 'card: ' + self.title + ', priority: ' + str(self.priority)

def __repl__(self):
return 'card: ' + self.title + ', priority: ' + str(self.priority)


• 它是一种堆，也就是说，如果是小根堆，每个节点的值比2个孩子的值要小，如果是大根堆，就要大
• 它是左倾的，意思是说，永远保持左子树的深度要比右子树的要大，所以它是不平衡的树
• 建堆需要$O(n)$，插入和删掉都只需要$O(logn)$
• 在最坏情况下，它会退化成一个链表，每个节点都只有左子树，就是输入元素是逆序的情况下
• 只适合删除堆顶元素的情况，不能删除任意一个元素，这种操作也叫Extract-Min

import random
from collections import deque

class LeftistNode:
def __init__(self, val):
self.val = val
# distance是节点到右孩子的距离
self.distance = 0
self.left_child = None
self.right_child = None
def __str__(self):
return 'node:' + str(self.val)

class LeftistTree:
def __init__(self, arr):
self.root = None
for item in arr:
self.insert(item)

def insert(self, item):
node = LeftistNode(item)
self.root = self.merge(self.root, node)

def delete(self):
# 合并左右子树，相当于删除根节点
self.root = self.merge(self.root.left_child, self.root.right_child)

def merge(self, left, right):
if left == None:
return right
if right == None:
return left
if left.val > right.val:
left, right = right, left
# 总是从右子树生长
left.right_child = self.merge(left.right_child, right)
# 总是保持左子树深度最大
if left.left_child == None or left.left_child.distance < left.right_child.distance:
left.left_child, left.right_child = left.right_child, left.left_child
# 更新根节点到右子树的距离
if left.right_child == None:
left.distance = 0
else:
left.distance = left.right_child.distance + 1
return left

def show(self):
queue = deque([self.root])
while len(queue) > 0:
node = queue.popleft()
print(node.val)
if node.right_child != None:
queue.append(node.right_child)
if node.left_child != None:
queue.append(node.left_child)
print('')


arr = [
Card('开发注册功能', random.randint(2, 5)),
Card('开发登录功能', random.randint(2, 5)),
Card('优化查看详情功能', random.randint(2, 5)),
Card('重构下载文件功能', random.randint(2, 5)),
Card('重构项目结构', random.randint(2, 5)),
Card('开发列表查询功能', random.randint(2, 5)),
Card('开发用户管理功能', random.randint(2, 5)),
]
for item in arr:
print(item)
print('')
tree = LeftistTree(arr)
tree.show()

tree.insert(Card('紧急处理用户不能登录的bug', 1))
tree.show()

tree.delete()
tree.show()

tree.delete()
tree.show()

card: 开发注册功能, priority: 3
card: 开发登录功能, priority: 3
card: 优化查看详情功能, priority: 2
card: 重构下载文件功能, priority: 4
card: 重构项目结构, priority: 5
card: 开发列表查询功能, priority: 5
card: 开发用户管理功能, priority: 2

card: 优化查看详情功能, priority: 2
card: 开发用户管理功能, priority: 2
card: 重构下载文件功能, priority: 4
card: 开发注册功能, priority: 3
card: 开发列表查询功能, priority: 5
card: 重构项目结构, priority: 5
card: 开发登录功能, priority: 3

card: 紧急处理用户不能登录的bug, priority: 1
card: 优化查看详情功能, priority: 2
card: 开发用户管理功能, priority: 2
card: 重构下载文件功能, priority: 4
card: 开发注册功能, priority: 3
card: 开发列表查询功能, priority: 5
card: 重构项目结构, priority: 5
card: 开发登录功能, priority: 3

card: 优化查看详情功能, priority: 2
card: 开发用户管理功能, priority: 2
card: 重构下载文件功能, priority: 4
card: 开发注册功能, priority: 3
card: 开发列表查询功能, priority: 5
card: 重构项目结构, priority: 5
card: 开发登录功能, priority: 3

card: 开发用户管理功能, priority: 2
card: 开发注册功能, priority: 3
card: 重构下载文件功能, priority: 4
card: 开发登录功能, priority: 3
card: 开发列表查询功能, priority: 5
card: 重构项目结构, priority: 5