python堆排序heapq

Python堆排序heapq模块实现了一个适用于Python列表的最小堆排序算法。

堆是一种树形数据结构，其中子节点与父节点之间是一种有序关系。最大堆（大顶堆）中父节点大于或等于两个子节点，最小堆（小顶堆）父节点小于或等于两个子节点。Python的heapq模块实现了一个最小堆。

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。

堆

　　堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图：

同时，我们对堆中的结点按层进行编号，将这种逻辑结构映射到数组中就是下面这个样子

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

ok，了解了这些定义。接下来，我们来看看python中堆排序的基本思想及基本操作：

创建堆

创建堆有两种方式，heappush()和heapify()。

import heapq
data = [1,5,3,2,8,5]
heap = []

for n in data:
    heapq.heappush(heap, n)

如果数据已经存在于内存中，使用heapify()原地重新组织列表中的元素会更加高效。

import heapq

data = [1,5,3,2,8,5] 
heapq.heapify(data)

上述两种方法得到的堆是一样的。

还有一种merge()方法，可以从多个可迭代对象中创建一个堆，相当于heapq.heapify(itertools.chain(*iterables))

访问堆内容

堆创建好之后，可以使用heappop()删除有最小值的元素。

import heapq
data = [1,5,3,2,8,5] 
heapq.heapify(data) 

print（heapq.heappop(data)） # print 1

如果希望在一个操作中删除现有最小元素并替换成新值，可以使用heapreplace()。

import heapq

data = [1,5,3,2,8,5] 
heapq.heapify(data) 
heapq.heapreplace(data,10)

堆的数据极值

heapq还包括两个检查可迭代对象的函数，查找其中包含的最大值与最小值的范围。

import heapq
data = [1,5,3,2,8,5]
print （heapq.nlargest(3, data)）
print （heapq.nsmallest(3, data)）

输出结果如下:

[8, 5, 5]

[1, 2, 3]

只有在n值比较小的情况下nlargest()和nsmallest()才比较高效。

这个两个函数还接受一个关键字参数key，用于更加复杂的数据结构中。

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

上面代码对每个元素进行比较时，会以price的值进行比较。

实战

实现堆排序

>>> from heapq import *

>>> def heapsort(iterable):
...     'Equivalent to sorted(iterable)'
...     h = []
...     for value in iterable:
...         heappush(h, value)
...     return [heappop(h) for i in range(len(h))]
...

由于堆中的元素可以为元组，所以可以对带权值的元素进行排序。

>>> from heapq import *

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')