Python教程

python-堆-heapd

本文主要是介绍python-堆-heapd,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

img

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)
这篇关于python-堆-heapd的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!