使用heapq获取Python堆中元素的深度

Question

我已经在这个问题上纠结了一天了。我有一组频率数据，想把它们放进一个堆里，我在用heapq这个模块。问题是，我想知道这些频率在哈夫曼树中各自的深度。 我尝试自己实现一个二叉树的类，但总是搞不对。有没有人知道怎么用Python的heapq模块找到堆中每个元素的深度？应该有更简单的方法吧？我这是为了编码用的。谢谢！

Answer 1

我觉得这个想法是，你可以用一个优先队列（用堆来实现）来构建哈夫曼树。或者，如果你只是需要树中每个项目的深度，你可以简单地增加一个合适的计数器：

import heapq

def huffman_depths(frequencies):
    depths = [0] * len(frequencies)

    heap = [(f, [i]) for i, f in enumerate(frequencies)]
    heapq.heapify(heap)

    while len(heap) > 1:
        f1, indexes1 = heapq.heappop(heap)         # pop two least frequent nodes
        f2, indexes2 = heapq.heappop(heap)

        frequency = f1 + f2                        # combine them
        indexes = indexes1 + indexes2

        for i in indexes:
            depths[i] += 1                         # increment depth count of each index

        heapq.heappush(heap, (frequency, indexes)) # push the combined result back on

    return depths