> 1);     @classmethod    def left(cls, i):        """左儿....">

当前位置:  编程技术>python

python计算最小优先级队列代码分享

    来源: 互联网  发布时间:2014-09-04

    本文导语:  代码如下:# -*- coding: utf-8 -*- class Heap(object):     @classmethod    def parent(cls, i):        """父结点下标"""        return int((i - 1) >> 1);     @classmethod    def left(cls, i):        """左儿子下标"""        return (i 0, "heap und...

代码如下:

# -*- coding: utf-8 -*-

class Heap(object):

    @classmethod
    def parent(cls, i):
        """父结点下标"""
        return int((i - 1) >> 1);

    @classmethod
    def left(cls, i):
        """左儿子下标"""
        return (i 0, "heap underflow"
        val = self[0]
        tail = heap_size - 1
        self[0] = self[tail]
        self.min_heapify(self, 0, tail)
        self.pop(tail)
        return val

    def decrease_key(self, i, key):
        """将i处的值减少到key,伪码如下:
        HEAP-DECREASE-KEY(A, i, key)
        1  if key > A[i]
        2    then error "new key is larger than current key"
        3  A[i] ← key
        4  while i > 1 and A[PARENT(i)] > A[i] // 不是根结点且父结点更大时
        5    do exchange A[i] ↔ A[PARENT(i)] // 交换两元素
        6       i ← PARENT(i) // 指向父结点位置

        T(n) = θ(lgn)
        """
        val = self[i]
        assert key 0 and self[parent(i)] > self[i]:
            self[i], self[parent(i)] = self[parent(i)], self[i]
            i = parent(i)

    def insert(self, key):
        """将key插入A,伪码如下:
        MIN-HEAP-INSERT(A, key)
        1  heap-size[A] ← heap-size[A] + 1 // 对元素个数增加
        2  A[heap-size[A]] ← +∞ // 初始新增加元素为+∞
        3  HEAP-DECREASE-KEY(A, heap-size[A], key) // 将新增元素减少到key

        T(n) = θ(lgn)
        """
        self.append(float('inf'))
        self.decrease_key(len(self) - 1, key)

if __name__ == '__main__':
    import random

    keys = range(10)
    random.shuffle(keys)
    print(keys)

    queue = MinPriorityQueue() # 插入方式建最小堆
    for i in keys:
        queue.insert(i)
    print(queue)

    print('*' * 30)

    for i in range(len(queue)):
        val = i % 3
        if val == 0:
            val = queue.extract_min() # 去除并返回最小元素
        elif val == 1:
            val = queue.minimum() # 返回最小元素
        else:
            val = queue[1] - 10
            queue.decrease_key(1, val) # queue[1]减少10
        print(queue, val)

    print([queue.extract_min() for i in range(len(queue))])


    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • Python GUI编程:tkinter实现一个窗口并居中代码
  • python学习手册中的python多态示例代码
  • Python获取网页编码的方法及示例代码
  • 用python代码做configure文件
  • Python 3 Tkinter教程之事件Event绑定处理代码实例
  • 生成Python代码的UML插件 PyUML
  • python中的深拷贝(deepcopy)和浅拷贝(copy)介绍及代码参考
  • python 布尔操作实现代码
  • python下xml解析库lxml最新版下载安装以及代码示例
  • python代码制作configure文件示例
  • Python类的构造函数,析构函数以及垃圾回收机制详细介绍及代码举例
  • python判断端口是否打开的实现代码
  • python字符串格式化输出及相关操作代码举例
  • python冒泡排序算法的实现代码
  • 数据结构:图(有向图,无向图),在Python中的表示和实现代码示例
  • python类型强制转换long to int的代码
  • python 简易计算器程序,代码就几行
  • python 快速排序代码
  • 打开电脑上的QQ的python代码
  • python中使用urllib2获取http请求状态码的代码例子
  • 一则python3的简单爬虫代码
  • Python不使用print而直接输出二进制字符串
  • 让python同时兼容python2和python3的8个技巧分享
  • Python中实现json字符串和dict类型的互转
  • 使用setup.py安装python包和卸载python包的方法
  • python异常信息堆栈输出到日志文件
  • 不小心把linux自带的python卸载了,导致安装一个依赖原python的软件不能安装,请问该怎么办?
  • python下用os.execl执行centos下的系统时间同步命令ntpdate
  • Python开发者社区整站源码 Pythoner
  • Python namedtuple对象json序列化/反序列化及对象恢复
  • python读取csv文件示例(python操作csv)


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3