如何檢查最大堆的孩子，找出哪個更大

我有一個數組表示，它擁有一個最大堆。對於'd'，'b'，'c'數組，它保留：b，d，c，儘管它應該是b，c，d。這是我的添加方法：如何檢查最大堆的孩子，找出哪個更大

public boolean add (E e) { 
    ensureCapacity(objectCount + 1); 
    pq[objectCount++] = e; 

    //percolate up 
    for (int i = objectCount - 1; i >= 0; i--) { 
    if (priorityComparator.compare(pq[i], pq[parent(i)]) >= 0) { 
      E tmp = pq[parent(i)]; 
      pq[parent(i)] = pq[i]; 
      pq[i] = tmp; 

    } 
    } 

    modCount++; 

    return true; 
    }

如果我接下來添加'a'，它會成功更改爲a，b，c，d。我該如何修復這個方法，以便它檢查左邊的孩子（2 * i + 1）和右邊的孩子（2 * i + 2），並根據哪個值具有更高優先級的隊列（a比b具有更高的優先級，等等）？

來源

2012-11-08 user1766888

我認爲你有一個MIN堆，而不是MAX堆。

我沒有看着你的代碼，但：

最小堆保障下列：

根總是分鐘（元素0你的情況）
樹始終是左排序（這是真實的任何堆）

輸出b，d，c是在你的情況完全合法的。嘗試刪除b並再次調用heapify，輸出將是c，d。

維基鏈接：http://en.wikipedia.org/wiki/Binary_heap

編輯： 如果你的情況考慮給比 'B' 'A' 更高的優先級，那麼是的，你確實有一個最大堆。

來源

2012-11-08 04:52:53

是的，a有更高的優先級。所以如果我有b，d在數組中，並且添加c我輸出b，d，c而不是b，c，d。當我添加'a'時它修復了它自己，但是爲了增加更多的值而變得更糟。對於a，b，c，d，e，f，g按照d，b，c，a，f，e，g的順序相加，返回數組a，b，c，d，f，e，g。 'f'不合適。 – user1766888

這就是我想解釋你的。堆不存儲排序順序。它只保證我的第一個元素（root）是MIN或MAX。現在當你移除一個元素時，它將確保下一個MIN/MAX將佔據根位置。請通過我給的Wiki鏈接，看看MAX和MIN堆的外觀。 –

這就是堆排序爲O（nlogn）的原因。每次heapify調用（將MIN/MAX放在根上的方法）需要O（logn）時間，並且您有n個這樣的元素。因此，O（nlogn）。 –

如何檢查最大堆的孩子，找出哪個更大

回答

相關問題