優先級隊列增加鍵opeartion

這裏是增加鍵操作的僞代碼假設我們使用的是馬克斯 - 堆優先級隊列增加鍵opeartion

if key < a[i] 
then return an error, because key is less than the current key 
else 
a[i] = key 
while i > 1 and a[parent(i)] < a[i] 
swap a[i] with a[parent(i)] 
i <- parent(i)

根據cormen算法的書，我不能減少的關鍵，如果我使用最大堆，但是阻止我這麼做的原因是什麼？我知道如果條件不會讓我減少關鍵。

但是假設我想以減少其在最大堆一定值時，這樣做，我申請heapify操作之後，然後我就可以減少，即使我使用MAX-堆的關鍵。這保證了最大堆的屬性

這個假設有什麼問題？

EDIT heapify功能類似於從一個給定的陣列構建堆功能。但不是從ZERO構建整個堆，我們可以從某個節點堆砌它。

來源

2016-03-14 Mohamed Horani

並不是每個人都熟悉這本書。添加「heapify」是什麼。 –

我記得當我讀這本書的時候，我有同樣的想法，呃，沒有？它仍然是O（log n）。 –

是的，它仍然是O（LG N），但它會起作用嗎？ –

該僞代碼是用於堆拉。這意味着節點只能走向根。如果您想減少密鑰，則需要實施推送操作（將節點向下推入堆中）。它非常相似，但您需要選擇節點的子節點之間的最大值。在你的書中查看，它應該在那裏。

所以，這是可能的，相當有效，但你需要更多的代碼。可能有我們不知道的外部需求。還要注意堆推是O（logn），heapify可能檢查整個堆，所以O（N）。

來源

2016-03-14 13:48:27 Sorin

通常在最大優先級隊列中，我們希望增加一個元素的優先級，以便首先提取它。

這就是爲什麼在一般最高優先級隊列API只有增加的密鑰的方法/功能，而不是減少密鑰。

但是你肯定可以在你自己的實現中使用一個Decrease-Key方法/函數。

來源

2017-12-04 15:12:27 amanmehara

優先級隊列增加鍵opeartion

回答

相關問題