当前位置:   article > 正文

python中的heapq_python的heapq

python的heapq

1.堆排序的应用

  • 寻找k个数中的最小值
  • 寻找n个数中的第k大的数

2.高级语言中提供封装好的堆这种结构

2.1 python中: import heapq

heapq内置模块位于./Anaconda3/Lib/heapq.py,提供基于堆的优先排序算法.

2.2 什么是堆?

堆的逻辑结构就是完全二叉树,并且二叉树中父节点的值小于等于该节点的所有子节点的值。这种实现可以使用 heap[k] <= heap[2k+1] 并且 heap[k] <= heap[2k+2] (其中 k 为索引,从 0 开始计数)的形式体现,对于堆来说,最小元素即为根元素 heap[0]。
注:python的这个模块默认是小顶堆。

2.3 heapq的使用

这个heapq是一个内置方法,所谓内置方法是指,它独立于对象,即不是某一个对象的方法。

  1. 初始化:可以通过 list 对 heap 进行初始化,或者通过 api 中的 heapify 将已知的 list 转化为 heap 对象。
    比如使用list对heap进行初始化:
 heap = []
  • 1
  1. heapq.py中提供的函数方法
heapq.heappush(heap, item)
  • 1

其中heap可以是初始化的一个堆(本身可以用一个空的列表),item是每次入堆的元素。因此还要结合循环使用。

heapq.heappop(heap):返回 root 节点,即 当前heap 中最小的元素。
  • 1

Example:

#1. c初始化一个堆
import heapq
heap = []
myarray = [2,1,5,4,3]
for item in myarray:
    heapq.heappush(heap,item)
print(len(heap))
print(heapq.heappop(heap))
print(len(heap))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

output:

5
1
4
  • 1
  • 2
  • 3
print([heapq.heappop(heap) for i in range(len(heap))])
  • 1
[1, 2, 3, 4, 5]
  • 1

结合上面测试可以简单写出堆排序:

def heapsort(myarray):
    heap = []
    for item in myarray:
        heapq.heappush(heap,item)
    return [heapq.heappop(heap) for i in range(len(myarray))]
    #或者return [heapq.heappop(heap) for i in range(len(myarray))]
lis = [2,1,5,4,3]
print(heapsort(lis))
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
[1, 2, 3, 4, 5]
  • 1

其他方法:

heapq.heapreplace(heap,item): python3中heappushpop的更高效版。
  • 1
heapq.heappushpop(heap, item):向 heap 中加入 item 元素,并返回 heap 中最小元素。
  • 1
heapq.heapify(x):将一个列表就地(in-place)时间复杂度 O(len(x)) 
  • 1
heapq.nlargest(n, iterable, key=None):返回可枚举对象中的 n 个最大值,并返回一个结果集 list,key 为对该结果集的操作。
  • 1
heapq.nsmallest(n, iterable, key=None):同上相反
  • 1
#method: use key to find price_min
portfolio = [{'name': 'IBM', 'shares': 100, 'price': 91.1},
              {'name': 'AAPL', 'shares': 50, 'price': 543.22},
              {'name': 'FB', 'shares': 200, 'price': 21.09},
              {'name': 'HPQ', 'shares': 35, 'price': 31.75},
              {'name': 'YHOO', 'shares': 45, 'price': 16.35},
              {'name': 'ACME', 'shares': 75, 'price': 115.65}]
cheap = heapq.nsmallest(3, portfolio, key=lambda s:s['price'])
print(cheap)
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
[{'name': 'YHOO', 'shares': 45, 'price': 16.35}, {'name': 'FB', 'shares': 200, 'price': 21.09}, {'name': 'HPQ', 'shares': 35, 'price': 31.75}]
  • 1
2.4 leetcode练习题:合并k个有序的链表
23. Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Example:
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

参考代码:
以下代码python可以解释通过,但是python3对heapq.heappush(heap, (node.val, node))不通过。

import heapq


# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        heap = []
        for node in lists:
            if node:
                #此处默认是按照元祖(node.val, node)上的第一个位置即node.val进行比较排序
                heapq.heappush(heap, (node.val, node))

        temp = ListNode(-1)
        head = temp
        while heap:
            smallestNode = heapq.heappop(heap)[1]
            temp.next = smallestNode
            temp = temp.next
            if smallestNode.next:
                heapq.heappush(heap, (smallestNode.next.val, smallestNode.next))
        return head.next
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
'
运行
2.5 python中调整堆的源码:
#将小元素上调,大元素下沉
def _siftdown(heap, startpos, pos):
    newitem = heap[pos]
    # Follow the path to the root, moving parents down until finding a place
    # newitem fits.
    while pos > startpos:
        parentpos = (pos - 1) >> 1
        parent = heap[parentpos]
        if newitem < parent:
            heap[pos] = parent
            pos = parentpos
            continue
        break
    heap[pos] = newitem
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
'
运行
2.6 关于python中的小于<
print((2,3)<(3,2))
print((3,2)<(2,3))
  • 1
  • 2
True
False
  • 1
  • 2

python 中的小于号,如果比较的是一个元组那么默认按照第一个位置进行比较

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/正经夜光杯/article/detail/1020064
推荐阅读
相关标签
  

闽ICP备14008679号