python中的堆排序peapq模块

heapq模块实现了python中的堆排序,并提供了有关方法。让用Python实现排序算法有了简单快捷的方式。

heapq的官方文档和源码:8.4.heapq-Heap queue algorithm

下面通过举例的方式说明heapq的应用方法

实现堆排序

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

heappush()

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

heappop()

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

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

heapq.heappushpop(heap, item)

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

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

heapq.heapify(x)

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

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

heapq.heapreplace(heap, item)

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

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

heapq.merge(*iterables)

举例:

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

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

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

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

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