美文网首页
heapq : 堆队列算法

heapq : 堆队列算法

作者: Hqmm | 来源:发表于2017-06-26 22:28 被阅读0次

    heapq : 堆队列算法

    Source code: Lib/heapq.py

    介绍

    • 这个模块提供了堆队列算法的实现,也称为优先队列算法。

    • 堆是一个特殊的二叉树(本文档中指的小顶堆,对应还有大顶堆),它的每个父结点的值小于等于它的两个孩子结点的值。
      该文中的堆是基于数组来实现的静态二叉树,对于数组中的每个元素

    heapq.merge(\*iterables, key=None, reverse=False)

    • 合并多个已排序(升序)的序列,返回一个可迭代对象
    • 功能和sorted(itertools.chain(*iterables))类似,但是它返回的是可迭代对象,它不会将所有的数据一次性放到内存里面,并且以输入的序列必须是
      排序、升序为前提
    • 有两个可选参数:
      • key参数制定了一个key函数,该函数用来指定输入序列中用来排序的元素;
      • reverse是一个bool值,若为true,则合并之后的元素倒排
        eg:
    a = [3, 1, 5, 7]
    b = [2, 4, 6, 8]
    c = merge(a, b)    
    for item in c:
        print(item, sep=" ", end=" "
    output:
      1 2 3 4 5 6 7 8  
    

    基础的例子

    • 堆排序可以通过将所有的元素压入堆中,然后每次从小顶堆中取出最小的元素(即二叉树中的根节点):

       def heapsort(iterable):
       h = []
       for value in iterable:
           heappush(h, value)
       return [heappop(h) for i in range(len(h))]
      
       heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
      
    • 上述的堆排序和内置sorted(iterable)函数很像,但是该堆排序不是稳定的,而sorted(iterable)是稳定的排序;

    • 堆元素可以是元组。这可以用于像任务优先级中,选取某个属性来作为当前的比较值:

      h = []
      heappush(h, (5, 'write code'))
      heappush(h, (7, 'release product'))
      heappush(h, (1, 'write spec'))
      heappush(h, (3, 'create tests'))
      heappop(h)
      

    相关文章

      网友评论

          本文标题:heapq : 堆队列算法

          本文链接:https://www.haomeiwen.com/subject/enfscxtx.html