在Java中實現Comparable的堆

我有一個充滿雙精度的數組，我想將這些雙精度數據保存在堆中。問題是我需要保持數組索引的記錄。在Java中實現Comparable的堆

Double[] array = new Double[n]; //imagine it's filled with doubles

現在我有一個PriorityQueue：

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(); //Integer because it's an heap of indexes

我想增加數組堆的每一個元素，但我要保證指數的紀錄。所以，想象我添加索引0到堆：

The heap stores 0, but uses array[0] to compare and sort it. 
Not index 0 itself, that's just like a class index. Stores v but compares v.value

當我從堆值：

Imagine I do heap.pull(); 
The heap returns me index 0, and then I will know the value is array[0].

我能做到這一點具有可比性？

來源

2014-12-06 Pedro B

我想知道你認爲「堆」在這種情況下意味着什麼。該術語通常用於指用於內存分配和垃圾收集的空間，而不是優先級隊列。我也認爲這是一個XY問題 - 你問我們是否可以使用特定的半編碼解決方案，而不告訴我們你想解決什麼問題......答案可能是這樣解決問題的方法是錯誤的，但我們無法用你給我們的答案來回答。就目前而言，我必須投票表決「接近不清」。 – keshlam 2014-12-06 22:24:33

此外，可以比較的對象，你想比較，而不是容器，所以它可能不是你要找的。答案可能是創建一個新類，而不是直接使用雙精度和整數。 – keshlam 2014-12-06 22:26:47

這個問題被正確解釋了，heap在priorityqueue中確實有一個應用程序，我寫的是一個我想要做的算法，所以我可以在Java中找到一個解決方案。我現在將單獨找到它，然後在這裏寫下，以便您可以看到我的問題並不清楚！ – 2014-12-06 22:55:25

我希望我能很好地理解你的問題。嘗試運行下面的示例。看看你是否瞭解它，如果這是你正在尋找的行爲。

int n = 10; 
final double[] arr = new double[n]; 
for (int i = 0; i < n; ++i) { 
    arr[i] = Math.random() * 100; 
} 
PriorityQueue<Integer> queue = new PriorityQueue<>(n, new Comparator<Integer>() { 
    @Override 
    public int compare(Integer o1, Integer o2) { 
     return (int) (arr[o1] - arr[o2]); 
    } 
}); 

for (int i = 0; i < n; ++i) { 
    queue.add(i); 
} 

System.out.println(Arrays.toString(arr)); 
System.out.println(queue.toString());

注意這會導致一個OutOfBoundsException速度非常快，當你添加了一些意想不到的PriorityQueue。

來源

2014-12-06 23:09:12 martijnn2008

在Java中實現Comparable的堆

回答

相關問題