關於BinaryHeap，如何確定數組的初始大小？

public BinaryHeap(AnyType [ ] items) { 
    currentSize = items.length; 
    array = (AnyType[]) new Comparable[ (currentSize + 2) * 11/10 ]; 

    int i = 1; 
    for(AnyType item : items) 
     array[ i++ ] = item; 
    buildHeap(); 
}

爲什麼是array.length = (currentSize + 2) * 11 /10？關於BinaryHeap，如何確定數組的初始大小？

來源

2013-03-22 Accelerator

無法理解你的問題，什麼是'新可比[[currentSize + 2] * 11/10]' – 2013-03-22 13:20:11

我不知道，它也似乎是錯的。通常，二進制堆中的數組被分配爲2^k的大小，使得2^k> currentSize – 2013-03-22 13:20:30

@KugathasanAbimaran Anytype擴展了Comparable <？超級AnyType>這就是爲什麼我新的Comparable。 – Accelerator 2013-03-22 14:22:49

我會解釋它是這樣的：

currentSize + 2 - 這是確保兩個元素將被添加到堆，由兩個
(currentSize + 2) * 11/10增加容量 - 增加10％的產能

事情是，這樣的堆實現具有有限的容量 - 受限於分配數組的長度。當你插入((currentSize + 2) * 11/10 + 1) th元素時，你需要調整數組的大小，這可能是一個昂貴的操作。特別是如果你總是通過增加舊的數組長度來調整大小。

它看起來像代碼的作者想確保數組的大小足以容納所有可能添加到它的元素。

編輯：

爲Ivaylo Strandjev在評論中提到的，通常的方式來設置堆大小是選擇k這樣2^k > currentSize。如果輸入項目的大小足夠大，代碼的作者可能不會選擇該方法：

例如，大多數時候預期的輸入大小是〜1200，峯值是1500，而初始輸入大小是1025個元素。按照通常的方法，你必須選擇k = 11 - > size是2048，但這意味着你浪費了（2048 - 1500 = 548）大小的AnyType對象字節在內存中。

來源

2013-03-22 13:57:46 linski

我很感謝你的幫助 – Accelerator 2013-03-22 14:18:52

我歡迎，np :) – linski 2013-03-22 14:21:54

關於BinaryHeap，如何確定數組的初始大小？

回答

相關問題