不小心看到一种数据结构,叫左偏堆,又叫左偏树,据说跟二叉堆一样,可以实现优先队列的功能,而且比二叉堆实现起来简单,于是研究了一下。

需求

优先队列的应用是非常广泛的,工作中还没遇到过这种需求,所以我现在制造一个需求,假设现在在开发一个项目管理系统,我们每天都要用的那种,每个任务都有优先级,我们肯定是先做优先级高的任务,再做优先级低的任务,由于插需求的事情经常发生,当一个需求插入时,我们要实现一个功能:优先级最高的排在看板的最顶部,当任务移走时,下一个优先级最高的排在最前面。

实现

看板的一列,我们可以看做是一个列表,每个元素,我给它定义成一个类Card,它有2个成员: title和priority,为了遵循习惯,priority越小的优先级越高, 优先级取值范围是1~5。

定义如下:

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

可以看出来,建堆之后,优先级最高的是为2的任务,这个时候插入了一个bug,要紧急处理,优先级为1,堆顶元素就变成这个bug了,处理完这个bug之后,移走,相当于删除掉,优先级最高的又变成优先级2的任务了,再移走,又是下一个,说明我们已经实现了优先队列,并且满足了这个需求,更有趣的是,这个左倾树的实现居然这么简单!!

参考资料