我試圖在Java中實現Min Heap,但我遇到了插入和刪除元素的問題(在最後插入,刪除根分鐘)。它似乎大部分工作(我使用程序來直觀地顯示堆,並已經打印出新的根,當min已被刪除,類似的東西)。使用數組實現Min堆:插入和刪除Min(帶有重複項)
我的問題是,出於某種原因,當添加一個新項目時,根不會切換爲新項目,但我無法弄清楚爲什麼。此外,似乎這只是存在大量重複時的問題,堆似乎不能完全保持順序(父項比子項小)。大多數情況下,它確實如此。只是偶爾它不會,對我來說它似乎是隨機的。
這是用泛型完成的,基本上遵循大多數算法。對於一個事實我知道的其他一切都是有效的,這對這兩種方法肯定是一個問題。
public void insert(T e) {
if (size == capacity)
increaseSize(); //this works fine
last = curr; //keeping track of the last index, for heapifying down/bubbling down when removing min
int parent = curr/2;
size++; //we added an element, so the size of our data set is larger
heap[curr] = e; //put value at end of array
//bubble up
int temp = curr;
while (temp > 1 && ((Comparable<T>) heap[temp]).compareTo(heap[parent]) < 0) { //if current element is less than the parent
//integer division
parent = temp/2;
swap(temp, parent); //the swapping method should be correct, but I included it for clarification
temp = parent; //just moves the index value to follow the element we added as it is bubbled up
}
curr++; //next element to be added will be after this one
}
public void swap(int a, int b){
T temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
public T removeMin() {
//root is always min
T min = heap[1];
//keep sure array not empty, or else size will go negative
if (size > 0)
size--;
//put last element as root
heap[1] = heap[last];
heap[last] = null;
//keep sure array not empty, or else last will not be an index
if (last > 0)
last--;
//set for starting at root
int right = 3;
int left = 2;
int curr = 1;
int smaller = 0;
//fix heap, heapify down
while(left < size && right < size){ //we are in array bounds
if (heap[left] != null && heap[right] != null){ //so no null pointer exceptions
if (((Comparable<T>)heap[left]).compareTo(heap[right]) < 0) //left is smaller
smaller = left;
else if (((Comparable<T>)heap[left]).compareTo(heap[right]) > 0) //right is smaller
smaller = right;
else //they are equal
smaller = left;
}
if (heap[left] == null || heap[right] == null)//one child is null
{
if (heap[left] == null && heap[right] == null)//both null, stop
break;
if (heap[left] == null)//right is not null
smaller = right;
else //left is not null
smaller = left;
}
if (((Comparable<T>)heap[curr]).compareTo(heap[smaller]) > 0)//compare smaller or only child
{
swap(curr,smaller); //swap with child
curr = smaller; //so loop can check new children for new placement
}
else //if in order, stop
break;
right = 2*curr + 1; //set new children
left = 2*curr;
}
return min; //return root
}
在方法聲明的任何變量是全球性的,我知道有幾件事情可能是多餘的,就像當前整個/最後/溫度在添加的情況,所以我感到很抱歉。我試圖讓所有的名字都自我解釋,並解釋我在removeMin中做的所有檢查。任何幫助都會受到瘋狂的讚賞,我已經儘可能地尋找和調試了。我想我在這裏只是從根本上失去了一些東西。
您是否正在使用IDE,以便您可以調試您的代碼? – Luciano 2012-04-26 23:54:26
是的,我使用eclipse,所以我可以調試。我也一直在使用GraphViz將堆顯示爲樹狀結構。老實說,我並不是最擅長使用調試器,並且通常在打印語句方面有更多的運氣,所以我可能會因爲這種無能爲力而錯過了一些東西。 – arsparfven 2012-04-26 23:56:33
這是功課嗎? – 2012-04-27 01:58:48