我试着用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 = 1heap.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;

07-24 19:14
查看更多