了解如何在Python中创建堆

Question

Python中的collections.Count.most_common函数使用heapq模块来返回文件中最常见单词的计数。

我已经找到了heapq.py这个文件，但是我很难理解如何根据单词来创建/更新堆。

所以，我认为理解它的最好方法就是弄清楚如何从头创建一个堆。

有人可以提供一个伪代码来创建一个代表字数的堆吗？

Answer 1

这是代码稍加修改的版本在这里找到：http://code.activestate.com/recipes/577086-heap-sort/

def HeapSort(A,T): 
    def heapify(A): 
     start = (len(A) - 2)/2 
     while start >= 0: 
      siftDown(A, start, len(A) - 1) 
      start -= 1 

    def siftDown(A, start, end): 
     root = start 
     while root * 2 + 1 <= end: 
      child = root * 2 + 1 
      if child + 1 <= end and T.count(A[child]) < T.count(A[child + 1]): 
       child += 1 
      if child <= end and T.count(A[root]) < T.count(A[child]): 
       A[root], A[child] = A[child], A[root] 
       root = child 
      else: 
       return 

    heapify(A) 
    end = len(A) - 1 
    while end > 0: 
     A[end], A[0] = A[0], A[end] 
     siftDown(A, 0, end - 1) 
     end -= 1 


if __name__ == '__main__': 
    text = "the quick brown fox jumped over the the quick brown quick log log" 
    heap = list(set(text.split())) 
    print heap 

    HeapSort(heap,text) 
    print heap 

输出

['brown', 'log', 'jumped', 'over', 'fox', 'quick', 'the'] 
['jumped', 'fox', 'over', 'brown', 'log', 'the', 'quick'] 

您可以观察程序在这里 http://goo.gl/2a9Bh

Answer 2

在Python 2.x和3.x，通过可导入的库heapq支持堆。它提供了许多函数来处理Python列表中建模的堆数据结构。 例子：

>>> from heapq import heappush, heappop 
>>> heap = [] 
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] 
>>> for item in data: 
     heappush(heap, item) 

>>> ordered = [] 
>>> while heap: 
     ordered.append(heappop(heap)) 

>>> ordered 
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9] 
>>> data.sort() 
>>> data == ordered 
True 

你可以找到更多关于堆函数：heappush, heappop, heappushpop, heapify, heapreplace在heap python docs。

Answer 3

下面是基于Sedgewick

另一变型堆被在阵列，其中，如果一个节点是在K，它的儿童在2内部表示* k和2 * K + 1中的阵列的第一个元素不被使用，使数学更方便。

要将新元素添加到堆中，请将其追加到数组的末尾，然后反复调用游动，直到新元素在堆中找到它的位置。

要删除根，请将其与数组中的最后一个元素进行交换，将其删除，然后调用接收器，直到交换元素找到它的位置。

swim(k): 
    while k > 1 and less(k/2, k): 
    exch(k, k/2) 
    k = k/2 

sink(k): 
    while 2*k <= N: 
    j = 2*k 
    if j < N and less(j, j+1): 
     j++ 
    if not less(k, j): 
     break 
    exch(k, j) 
    k = j 

这里的堆插入物的可视化，将所述字母表的第一15个字母：[AO]