首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >了解如何在Python中创建堆

了解如何在Python中创建堆
EN

Stack Overflow用户
提问于 2012-10-05 23:40:29
回答 3查看 53.1K关注 0票数 28

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

我已经跟踪了heapq.py文件,但是我在理解堆是如何创建/更新单词方面遇到了一些问题。

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

有人能提供一个伪代码来创建一个表示字数统计的堆吗?

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2012-10-06 00:01:39

这是代码的一个稍微修改的版本,可以在这里找到:http://code.activestate.com/recipes/577086-heap-sort/

代码语言:javascript
复制
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

输出

代码语言:javascript
复制
['brown', 'log', 'jumped', 'over', 'fox', 'quick', 'the']
['jumped', 'fox', 'over', 'brown', 'log', 'the', 'quick']

你可以在这里可视化这个程序http://goo.gl/2a9Bh

票数 14
EN

Stack Overflow用户

发布于 2012-10-06 13:19:24

在Python2.x和3.x中,通过一个可导入的库heapq来支持堆。它提供了许多函数来处理在Python列表中建模的堆数据结构。示例:

代码语言:javascript
复制
>>> 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

您可以找到有关堆函数的更多信息:heap python docs中的heappush, heappop, heappushpop, heapify, heapreplace

票数 36
EN

Stack Overflow用户

发布于 2014-04-09 08:59:43

这是另一个基于Sedgewick的变体

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

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

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

代码语言:javascript
复制
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

下面是heap insert的可视化,插入字母表的前15个字母: a-o

票数 16
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/12749622

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档