我有一個實現為堆的索引最小優先級隊列。刪除索引元素時，代碼為： public void delete(int i) { if (i < 0 || i >= maxN) throw new IllegalArgumentException(); if (!contains(i)) throw new NoSuchElementException("index is not in the priority queue"); int index = qp[i]; exch(index, n--); swim(index); // Why is this needed? sink(index); keys[i] = null; qp[i] = -1;}其余代碼可以在這里找到：https : //algs4.cs.princeton.edu/24pq/IndexMinPQ.java.html由于pq[N] 是 中的最后一個元素pq[]，并且它與元素 at 交換pq[i]（將被刪除），這是否意味著pq[i]交換后的值大于或等于pq[i]交換前的值？問題是為什么我們必須打電話swim(i)而不是sink(i)單獨打電話？什么情況下需要swim(i)在swap后調用？（有3個陣列，qp[]并keys[]與相應的索引，以及pq[]使得qp[pq[i]]= pq[qp[i]]= i。）
1 回答
湖上湖
TA貢獻2003條經驗 獲得超2個贊
由于 pq[N] 是 pq[] 中的最后一個元素，并且它與 pq[i] 處的元素（將被刪除）交換，這是否意味著交換后 pq[i] 處的值交換前是否大于或等于 pq[i]？
不，這不一定是真的。有效堆的唯一要求是子級不能大于其父級。雖然這意味著在第一位置的元素是最小的，但它并不意味著在最后位置的元素是最大的?？紤]以下堆：
1
10 2
15 18 5 3
16 17 19 20 7 8 6 4
pq[N]是4，但該堆中有很多元素比它大。假設我們想15通過將其替換為 來刪除4。 4小于10，因此必須向上移動樹（使用swim）。
添加回答
舉報
0/150
提交
取消