使用陣列VS實現堆（ADT） LinkedList的

在我的數據結構課程，我需要實現與下列時間二元堆 - 複雜性要求：使用陣列VS實現堆（ADT） LinkedList的

查找最大值 - O（1）
插入 - O（LG N）
刪除最大 - O（LG n）的

現在我認爲實現此以下面的方式使用的數組：堆的根是在編曲[1]（第一索引）。 Arr [i]的孩子在Arr [2i]和Arr [2i + 1]（2個孩子）。在這個實現中，我將在O（1）中獲得查找最大值，在O（n）中刪除最大值並插入O（lg n）中，但有一個例外 - 如果在數組滿了時需要插入，我將不得不調整數組並且將「花費」我O（n），因此所有邊緣案例的插入總成本將爲O（n）而不是O（log n）。

是否有其他的實現方式可以滿足所有複雜的需求？我想也許試圖用一個LinkedList而不是一個數組來實現，但插入仍然是O（n）。任何有關實施的建議都將非常受歡迎。

來源

2016-04-15 Noam

您的實施可以滿足要求。我假設，當你說刪除最大將採取O（n），你認爲你需要將整個陣列轉移到一個位置？在這種情況下，你實際需要做的是擁有第二大元素，像他們所說的那樣。這隻需要O（lgn）時間。

另外調整大小不會經常發生，所以分期付款運行時仍然是O（lgn）。 See here。

來源

2016-04-15 19:16:25

謝謝你，其實我的意思是通過使用你提到的'游泳'技術來寫出「刪除最大值」是O（log n）。我的問題是插入 - 我知道分期付款的運行時間是O（日誌n），但我需要最壞的情況下運行時間爲O（日誌n），這是什麼讓我想，也許我不應該實現這個堆使用數組但以不同的方式... – Noam

好吧，我明白了。來自維基百科文章的一個想法*分期分析的動機是，每個操作的最壞情況運行時間可能過於悲觀*。我認爲你有正確的實施。請參閱[本簡報]（http://algs4.cs.princeton.edu/lectures/24PriorityQueues.pdf）。你當前的實現仍然被認爲是O（lgn）。 –

好的。所以我會試着離開這個實現。謝謝 – Noam

使用陣列VS實現堆（ADT） LinkedList的

回答

相關問題