python中的堆排序peapq模块

heapq模块实现了python中的堆排序，并提供了有关方法。让用Python实现排序算法有了简单快捷的方式。 heapq的官方文档和源码：8.4.heapq-Heap queue algorithm 下面通过举例的方式说明heapq的应用方法

实现堆排序

  1.   1. #! /usr/bin/evn python
  2.     2. #coding:utf-8
  3.     3.   4. from heapq import *
  4.     5.   6. def heapsort(iterable):
  5.     7.     h = []
  6.     8.     for value in iterable:
  7.     9.         heappush(h,value)
  8.     10.     return [heappop(h) for i in range(len(h))]
  9.     11.   12. if __name__=="__main__":
  10.     13.     print heapsort([1,3,5,9,2])

heappush()

heapq.heappush(heap, item):将item压入到堆数组heap中。如果不进行此步操作，后面的heappop()失效

heappop()

heapq.heappop(heap):从堆数组heap中取出最小的值，并返回。

  1.   1. >>> h=[]                    #定义一个list
  2.     2. >>> from heapq import *     #引入heapq模块
  3.     3. >>> h
  4.     4. []
  5.     5. >>> heappush(h,5)               #向堆中依次增加数值
  6.     6. >>> heappush(h,2)
  7.     7. >>> heappush(h,3)
  8.     8. >>> heappush(h,9)
  9.     9. >>> h                           #h的值
  10.     10. [2, 5, 3, 9]
  11.     11. >>> heappop(h)                  #从h中删除最小的，并返回该值
  12.     12. 2
  13.     13. >>> h
  14.     14. [3, 5, 9]
  15.     15. >>> h.append(1)                 #注意，如果不是压入堆中，而是通过append追加一个数值
  16.     16. >>> h                           #堆的函数并不能操作这个增加的数值，或者说它堆对来讲是不存在的
  17.     17. [3, 5, 9, 1]
  18.     18. >>> heappop(h)                  #从h中能够找到的最小值是3,而不是1
  19.     19. 3
  20.     20. >>> heappush(h,2)               #这时，不仅将2压入到堆内，而且1也进入了堆。
  21.     21. >>> h
  22.     22. [1, 2, 9, 5]
  23.     23. >>> heappop(h)                  #操作对象已经包含了1
  24.     24. 1

heapq.heappushpop(heap, item)

是上述heappush和heappop的合体，同时完成两者的功能.注意：相当于先操作了heappush(heap,item),然后操作heappop(heap)

  1.   1. >>> h
  2.     2. [1, 2, 9, 5]
  3.     3. >>> heappop(h)
  4.     4. 1
  5.     5. >>> heappushpop(h,4)            #增加4同时删除最小值2并返回该最小值，与下列操作等同：
  6.     6. 2                               #heappush(h,4),heappop(h)
  7.     7. >>> h
  8.     8. [4, 5, 9]

heapq.heapify(x)

x必须是list，此函数将list变成堆，实时操作。从而能够在任何情况下使用堆的函数。

  1.   1. >>> a=[3,6,1]
  2.     2. >>> heapify(a)                  #将a变成堆之后，可以对其操作
  3.     3. >>> heappop(a)
  4.     4. 1
  5.     5. >>> b=[4,2,5]                   #b不是堆，如果对其进行操作，显示结果如下
  6.     6. >>> heappop(b)                  #按照顺序，删除第一个数值并返回,不会从中挑选出最小的
  7.     7. 4
  8.     8. >>> heapify(b)                  #变成堆之后，再操作
  9.     9. >>> heappop(b)
  10.     10. 2

heapq.heapreplace(heap, item)

是heappop(heap)和heappush(heap,item)的联合操作。注意，与heappushpop(heap,item)的区别在于，顺序不同，这里是先进行删除，后压入堆

  1.   1. >>> a=[]
  2.     2. >>> heapreplace(a,3)            #如果list空，则报错
  3.     3. Traceback (most recent call last):
  4.     4. File "<stdin>", line 1, in <module>
  5.     5. IndexError: index out of range
  6.     6. >>> heappush(a,3)
  7.     7. >>> a
  8.     8. [3]
  9.     9. >>> heapreplace(a,2)            #先执行删除（heappop(a)->3),再执行加入（heappush(a,2))
  10.     10. 3
  11.     11. >>> a
  12.     12. [2]
  13.     13. >>> heappush(a,5)  
  14.     14. >>> heappush(a,9)
  15.     15. >>> heappush(a,4)
  16.     16. >>> a
  17.     17. [2, 4, 9, 5]
  18.     18. >>> heapreplace(a,6)            #先从堆a中找出最小值并返回，然后加入6
  19.     19. 2
  20.     20. >>> a
  21.     21. [4, 5, 9, 6]
  22.     22. >>> heapreplace(a,1)            #1是后来加入的，在1加入之前，a中的最小值是4
  23.     23. 4
  24.     24. >>> a
  25.     25. [1, 5, 9, 6]

heapq.merge(*iterables)

举例：

  1.   1. >>> a=[2,4,6]         
  2.     2. >>> b=[1,3,5]
  3.     3. >>> c=merge(a,b)
  4.     4. >>> list(c)
  5.     5. [1, 2, 3, 4, 5, 6]

在归并排序中详细演示了本函数的使用方法。

heapq.nlargest(n, iterable[, key]),heapq.nsmallest(n, iterable[, key])

获取列表中最大、最小的几个值。

  1.   1. >>> a   
  2.     2. [2, 4, 6]
  3.     3. >>> nlargest(2,a)
  4.     4. [6, 4]

整理人：豆包AI助手