我试着用Java构建一个minheap,这是我的代码:
public class MyMinHeap {
private ArrayList<Node> heap;
public MyMinHeap() {
heap = new ArrayList<Node>();
}
public MyMinHeap(ArrayList<Node> nodeList) {
heap = nodeList;
buildHeap();
}
public void buildHeap() {
int i = heap.size() / 2;
while (i >= 0) {
minHeapify(i);
i--;
}
}
public Node extractMin() {
if (heap.size() <= 0) return null;
Node minValue = heap.get(0);
heap.set(0, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
minHeapify(0);
return minValue;
}
public String toString() {
String s = "";
for (Node n : heap) {
s += n + ",";
}
return s;
}
public void minHeapify(int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < heap.size() - 1 && lessThan(left, smallest))
smallest = left;
if (right < heap.size() - 1 && lessThan(right, smallest))
smallest = right;
if (smallest != i) {
swap(smallest, i);
minHeapify(smallest);
}
}
private void swap(int i, int j) {
Node t = heap.get(i);
heap.set(i, heap.get(j));
heap.set(j, t);
}
public boolean lessThan(int i, int j) {
return heap.get(i)
.compareTo(heap.get(j)) < 0;
}
public static void main(String[] args) {
char[] chars = {'a', 'b', 'c', 'd', 'e', 'f'};
int[] freqs = {45, 13, 12, 16, 9, 5};
ArrayList<Node> data = new ArrayList<Node>();
for (int i = 0; i < chars.length; i++) {
data.add(new Node(chars[i], freqs[i]));
}
MyMinHeap heap = new MyMinHeap(data);
System.out.println("print the heap : " + heap);
for (int i = 0; i < chars.length; i++) {
System.out.println("Smallest is :" + heap.extractMin());
}
}
}
输出应为:5,9,12,13,16,45,
但我得到的是:9,13,12,16,45
我已经调试过了,但还是搞不懂,有人帮忙吗?谢谢。
最佳答案
问题出在minHeapify
函数中。你有:
public void minHeapify(int i) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int smallest = i;
if (left < heap.size() - 1 && lessThan(left, smallest))
smallest = left;
if (right < heap.size() - 1 && lessThan(right, smallest))
smallest = right;
现在,假设初始数组列表是
{3,2}
,并调用minHeapify(0)
。left = 2 * i + 1; // = 1
right = 2 * i + 2; // = 2
smallest = i; // 0
你的下一个陈述:
if (left < heap.size() - 1 && lessThan(left, smallest))
此时,
left = 1
和heap.size()
返回2。所以left
不小于heap.size() - 1
。因此,您的函数退出而不交换这两个项目。从条件句中删除
- 1
,给出: if (left < heap.size() && lessThan(left, smallest))
smallest = left;
if (right < heap.size() && lessThan(right, smallest))
smallest = right;