我正在尝试用 Java 实现最小堆,但我在插入和删除元素时遇到问题(在末尾插入,删除根作为最小值)。它似乎在大多数情况下都有效(我使用一个程序来直观地显示堆,并在删除 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
}
任何未在方法中声明的变量都是全局变量,我知道有几件事可能是多余的,例如 add 中的整个当前/最后/临时情况,所以我对此感到抱歉。我试图让所有的名字都能 self 解释,并解释我在 removeMin 中所做的所有检查。任何帮助将不胜感激,我已经尽我所能查找和调试。我想我只是在这里从根本上遗漏了一些东西。
最佳答案
只是为了帮助您调试,您应该简化代码。 “last”变量发生了一些奇怪的事情。同样在 'insert' 中,当你执行循环时,可能 temp 应该变为 0,即
while (temp >= 0 &&......
关于java - 使用数组 : Insert and Remove Min (with duplicates) 实现最小堆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/10342766/