python - 了解如何在 Python 中创建堆

Question

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

我已经通过heapq.py文件进行了跟踪，但是我在理解堆是如何创建/更新相对于单词的让我们说的时候遇到了一些麻烦。

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

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

Answer 1

在 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 2

这是基于Sedgewick的另一个变体

堆在内部表示在一个数组中，如果一个节点位于 k，它的子节点位于 2*k 和 2*k + 1。不使用数组的第一个元素，以使数学更方便。

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

要删除根，将它与数组中的最后一个元素交换，删除它，然后调用 sink 直到交换的元素找到它的位置。

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]

Answer 3

这是此处代码的略微修改版本：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 4

您的困惑可能来自 Python 模块heapq没有将堆定义为具有自己的方法（例如在 a或 a中）的数据类型（类）。相反，它提供了可以在 Python 上运行的函数。dequelistlist

最好将其heapq视为一个提供一组算法（方法）的模块，以将列表解释为堆并相应地操作它们。请注意，在内部将堆表示为数组heapq（作为抽象数据结构）是很常见的，并且 Python 已经有用于该目的的列表，因此仅提供将列表操作为堆的方法是有意义的。

让我们看一个例子。从一个简单的 Python 列表开始：

>>> my_list = [2, -1, 4, 10, 0, -20]

heapq要使用from创建一个堆，my_list我们只需要调用heapify它简单地重新排列列表的元素以形成一个最小堆：

>>> import heapq
>>> # NOTE: This returns NoneType:
>>> heapq.heapify(my_list)

请注意，您仍然可以访问堆底层的列表，因为heapify所做的只是更改引用的值my_list：

>>> my_list
[-20, -1, 2, 10, 0, 4]

从持有的堆中弹出元素my_list：

>>> [heapq.heappop(my_list) for x in range(len(my_list))]
[-20, -1, 0, 2, 4, 10]