了解如何在Python中创建堆 [英] Understanding how to create a heap in Python

问题描述

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

The collections.Count.most_common function in Python uses the heapq module to return the count of the most common word in a file, for instance.

我已经遍历了heapq.py文件，但是在理解如何相对于假设的单词创建/更新堆方面遇到了一些麻烦.

I have traced through the heapq.py file, but I'm having a bit of trouble understanding how a heap is created/updated with respect to words let's say.

所以，我认为对我来说最好的理解方法是弄清楚如何从头开始创建堆.

So, I think the best way for me to understand it, is to figure out how to create a heap from scratch.

有人可以提供伪代码来创建表示字数的堆吗?

Can someone provide a pseudocode for creating a heap that would represent word count?

推荐答案

这是此处找到的代码的略微修改版本:

this is a slightly modified version of the code found here : 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

you can visualize the program here http://goo.gl/2a9Bh

这篇关于了解如何在Python中创建堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！