堆棧中使用heapq的元素的Python深度

我一直在研究這個問題一天。我有一個頻率列表，我想把它放在一堆。我使用heapq。問題在於，當放置在霍夫曼樹中時，可以找到每個頻率的深度。我試着實現我自己的類二叉樹，但我似乎無法正確。有沒有人知道如何找到堆中的每個元素的深度使用Python中的模塊heapq必須有一個更簡單的方法？我使用它進行編碼。謝謝！堆棧中使用heapq的元素的Python深度

來源

2014-03-27 user3349106

堆和霍夫曼樹是不一樣的東西，但你似乎可以用一個作爲替代另一個。你能更詳細地解釋一下你到底在找什麼嗎？你能顯示你當前的代碼嗎？二進制堆中的項的深度（如由heapq生成的）只是「floor（log2（index + 1））」。我不確定霍夫曼樹有什麼簡單的等價物。 – Blckknght

我正在尋找給定頻率列表的霍夫曼樹的代價。我被告知我可以使用heapq。要找到成本，您必須簡單地找到頻率的深度。我有一堆代碼theyre都沒用。仍在試圖弄清楚。 – user3349106

生病給你一個簡單的頻率l = [70,37,20,3]每個人的深度是1,2,3,3得到huffman編碼的代價是213.固定的編碼代價是260 – user3349106

我認爲這個想法是，你可以使用優先級隊列（用堆實現）來構建霍夫曼樹。或者，如果你只需要在樹中的項目的深處，你可以簡單地增加一個合適的計數器：

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

來源

2014-03-27 06:36:25 Blckknght

好的謝謝這幫了很大的忙！ – user3349106

堆棧中使用heapq的元素的Python深度

回答

相關問題