python-heapd

• python-heapd
  • heapq堆的常用方法
    • 堆类型的最大和最小值
      • heapq.nlargest(n,heap)
      • heapq.nsmallest(n,heap)
      • heapq.heapify(list)
      • heapq.heappop(heap)
      • heapq.heappush(heap, item)
      • heapq.heapreplace(heap.item)
      • heapq.heappushpop(list, item)
    • heapq.merge（…）
  • 使用heapq编写优先级队列

堆是非线性的树形的数据结构，有两种堆,最大堆与最小堆（heapq库中的堆默认是最小堆）

最大堆，树种各个父节点的值总是大于或等于任何一个子节点的值。

最小堆，树种各个父节点的值总是小于或等于任何一个子节点的值。

一般使用二叉树实现优先队列，算法复杂度logN

heapq堆的常用方法

堆类型的最大和最小值

怎样从一个集合中获得最大或者最小的 N 个元素列表

heapq.nlargest(n,heap)

• input: n个数，heap 堆数据
• return 最大最小元素列表

import heapq

numbers = [1, 4, 2, 100, 20, 50, 32, 200, 150, 8]
print(heapq.nlargest(4, numbers))

# 输出：[200, 150, 100, 50]

import heapq

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} ]
expensive = heapq.nlargest(2, portfolio, key=lambda s: s['price'])


print(expensive)

# [{'name': 'AAPL', 'shares': 50, 'price': 543.22}, {'name': 'ACME', 'shares': 75, 'price': 115.65}]

heapq.nsmallest(n,heap)

lis=[3, 5, 5, 9, 6, 6, 8, 99]
res=heapq.nsmallest(3,lis)
print(res)

# [3,5,5]

heapq.heapify(list)

直接将列表就地转换为堆,重新排列列表中的项,无返回值

• input: list >> heap
• return None

堆最有趣的属性是它的最小元素始终是第一个元素：heap [0]

numbers = [10, 4, 2, 100, 20, 50, 32, 200, 150, 8]
heap=heapq.heapify(numbers)  #将列表就地转换为堆
print(heap)
print(numbers)

# None
# [2, 4, 10, 100, 8, 50, 32, 200, 150, 20] #  堆的第一个元素一定是最小的那个值

heapq.heappop(heap)

删除并返回最小值，堆的特征是heap[0]永远是最小的元素

弹出并返回堆中的最小项，保持堆不变。如果堆是空的，则引发IndexError

numbers = [10, 4, 2, 100, 20, 50, 32, 200, 150, 8]
heapq.heappop(numbers)
# 删除最小的值最返回：2
print(numbers)
# 输出: [4, 8, 10, 100, 20, 50, 32, 200, 150]

heapq.heappop(numbers)
# 删除最小的值最返回：4
print(numbers)
# 输出: [8, 20, 10, 100, 150, 50, 32, 200]

heapq.heappush(heap, item)

向 heap 压入一个值

注：heap为定义堆，item增加的元素

import heapq
h = []
heapq.heappush(h,2)

print(h)
# [2]

heapq.heapreplace(heap.item)

先删除最小值，再添加新值

先 pop 最小元素，再压入 item，相当于先调用 heappop() 再调用heappush()；

先删除最小元素值，再添加新的元素值

list=[2, 5, 3, 9, 6, 5, 8, 99]

hppop=heapq.heapreplace(list,6)
print(hppp)
print(list)
# 2
# [3, 5, 5, 9, 6, 6, 8, 99]

list=[3, 5, 5, 9, 6, 6, 8, 99]
hppop=heapq.heapreplace(list,1)
print(hppop)
print(list)
# 1
# [3, 5, 5, 9, 6, 6, 8, 99]

heapq.heappushpop(list, item)

将 item 放入堆中，然后弹出并返回 heap 的最小元素， 该函数比先调用 heappush() 再调用 heappop() 效率更高

先添加新元素，再删除最小元素

list=[2, 5, 3, 9, 6, 5, 8, 99]

hppop=heapq.heappushpop(list,6)
print(hppp)
print(list)
# 2
# [3, 5, 5, 9, 6, 6, 8, 99]

list=[3, 5, 5, 9, 6, 6, 8, 99]
hppop=heapq.heappushpop(list,1)
print(hppop)
print(list)
# 1
# [3, 5, 5, 9, 6, 6, 8, 99]

heapq.merge（…）

返回顺序迭代器

import heapq
a = [1, 3, 7, 10]
b = [2, 5, 6, 11]
for c in heapq.merge(a, b):
    print(c)
    
1
2
3
5
6
7
10

使用heapq编写优先级队列

class PriorityQueue:
    def __init__(self):
        self.__queue = []
        self.__index = 0
        
    def push(self, item, priority):
        heapq.heappush(self.__queue, (-priority, self.__index, item))
        # 第一个参数：添加进的目标序列
        # 第二个参数：将一个元组作为整体添加进序列，目的是为了方便比较
        # 在priority相等的情况下，比较_index
        # priority为负数使得添加时按照优先级从大到小排序，因为堆排序的序列的第一个元素永远是最小的
        self.__index += 1
        
    def pop(self):
        # 返回按照-priority 和 _index 排序后的第一个元素(是一个元组)的最后一个元素(item)
        return heapq.heappop(self.__queue)[-1]
 
 
 
q = PriorityQueue()
q.push("bar", 2)
q.push("foo", 1)
q.push("gork", 3)
q.push("new", 1)
print(q.pop())
print(q.pop())
print(q.pop())
print(q.pop())
 
"""
gork  # 优先级最高
bar   # 优先级第二
foo   # 优先级与new相同，比较index，因为先加入，index比new小，所以排在前面
new
"""
 

有 1000 个无序的整数，希望使用最快的方式找出前 50 个最大的

import heapq


def heapsort(data, hp_size=3):
    h = []
    for i in range(len(data)):
        if i >= hp_size:
            heapq.heappushpop(h, data[i])  #先放入值，在弹出
        else:
            heapq.heappush(h, data[i])    
    return [heapq.heappop(h) for _ in range(len(h))]


res = heapsort([6,2,1,-4,9,4,0])
print(res)