優先級隊列數據結構

假設我有一個優先級隊列，它以遞增的順序移除元素，並且存儲在這個隊列中的元素是1, 1, 3, 0, 1。遞增順序是0然後1然後3，但有三個元素1 s。優先級隊列數據結構

當我打電話remove它會先刪除0，但如果我叫remove再次將它在同一時間刪除所有三個1 S，或者我需要調用remove三個單獨次，以去除所有的1元素。

在這樣的優先級隊列上調用remove是否刪除所有具有相同最小值的元素，或者每次調用時只會刪除一個元素？

2010-11-20 user472221

除非你說出你正在使用什麼實現，否則不是一個真正的問題。 – 2010-11-20 03:59:37

未分類數組 – user472221 2010-11-20 04:19:20

「未分類數組」？在那種情況下，你正在自己實現數據類型，所以你可以決定你想要做什麼...... – 2010-11-20 12:05:21

在優先級隊列中，通常刪除操作將刪除包含最大值的單個記錄。所以在你的情況下，這將是第二種選擇。不能保證移除的順序。任何具有「最大」值的鍵都將被刪除。另外，未分類數組是實現優先級隊列的錯誤數據結構。您通常會使用堆數據結構來獲取O（log（n））插入和刪除的保證。

2010-11-20 04:26:20 Naveen

典型的堆實現總是reheap樹因此將刪除0，1，1，1，然後3爲1將得到推動reheapification期間根..

我錯了？

編輯：你的情況是最小堆

2010-11-20 04:31:38

回答