设为首页 加入收藏

TOP

用Python实现数据结构之优先级队列(二)
2019-02-10 22:08:27 】 浏览:167
Tags:Python 实现 数据结构 优先 队列

j)
        if j > 0 and self.data[j] < self.data[parent]:
            self.swap(j, parent)
            self.upheap(parent)


    def downheap(self, j):
        """向下堆排序"""
        if self.has_left(j):
            left = self.left(j)
            small = left
            if self.has_right(j):
                right = self.right(j)
                if self.data[right] < self.data[left]:
                    small = right
            if self.data[small] < self.data[j]:
                self.swap(small, j)
                self.downheap(small)


    def __init__(self):
        self.data = []


    def __len__(self):
        return len(self.data)


    def add(self, key, value):
        """添加一个元素,并进行向上堆排序"""
        self.data.append(self.Item(key, value))
        self.upheap(len(self.data) - 1)


    def min(self):
        if self.is_empty():
            raise Empty('Priority queue is empty')
        item = self.data[0]
        return (item.key, item.value)


    def remove_min(self):
        if self.is_empty():
            raise Empty('Priority queue is empty')
        self.swap(0, len(self.data) - 1)
        item = self.data.pop()
        self.downheap(0)
        return (item.key, item.value)


python的heapq模块


Python标准包含了heapq模块,但他并不是一个独立的数据结构,而是提供了一些函数,这些函数吧列表当做堆进行管理,而且元素的优先级就是列表中的元素本身,除此之外它的模型与实现方式与刚才我们自己定义的基本相同


有以下函数:



用Python实现数据结构之优先级队列(二) https://www.cppentry.com/bencandy.php?fid=54&id=207800

首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇用Python实现数据结构之映射 下一篇Java中创建对象的五种方式