java 使用java构建最小堆

Building a min heap using java

提问by Vincent

I tried to build a minHeap using java, this is my code:

我尝试使用 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());
        }

    }
}

The output should be:5,9,12,13,16,45,

输出应该是：5,9,12,13,16,45,

but what I got is : 9,13,12,16,45

但我得到的是：9,13,12,16,45

I have debugged this but still can't figure out, anybody help? thanks a lot.

我已经调试了这个，但仍然无法弄清楚，有人帮忙吗？多谢。

采纳答案by Jim Mischel

The problem is in your minHeapifyfunction. You have:

问题出在您的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;

Now, let's say that your initial array list is {3,2}, and you call minHeapify(0).

现在，假设您的初始数组列表是{3,2}，并且您调用minHeapify(0).

left = 2 * i + 1;  // = 1
right = 2 * i + 2; // = 2
smallest = i;      // 0

Your next statement:

你的下一个声明：

if (left < heap.size() - 1 && lessThan(left, smallest))

At this point, left = 1, and heap.size()returns 2. So leftisn't smaller than heap.size() - 1. So your function exits without swapping the two items.

此时left = 1， 和heap.size()返回 2。所以left不小于heap.size() - 1。所以你的函数退出而不交换这两个项目。

Remove the - 1from your conditionals, giving:

- 1从您的条件中删除，给出：

    if (left < heap.size() && lessThan(left, smallest))
        smallest = left;

    if (right < heap.size() && lessThan(right, smallest))
        smallest = right;

回答by user3060544

Insert : When we insert into a min-heap, we always start by inserting the element at the bottom. We insert at the rightmost spot so as to maintain the complete tree property. Then, we "fix" the tree by swapping the new element with its parent, until we find an appropriate spot for the element. We essentially bubble up the minimum element. This takes 0 (log n) time, where n is the number of nodes in the heap.

插入：当我们插入最小堆时，我们总是从在底部插入元素开始。我们在最右边的位置插入以保持完整的树属性。然后，我们通过将新元素与其父元素交换来“修复”树，直到我们为该元素找到合适的位置。我们基本上冒泡了最小元素。这需要 0 (log n) 时间，其中 n 是堆中的节点数。

Extract Minimum Element : Finding the minimum element of a min-heap is easy: it's always at the top. The trickier part is how to remove it. (I n fact, this isn't that tricky.) First, we remove the minimum element and swap it with the last element in the heap (the bottommost, rightmost element). Then, we bubble down this element, swapping it with one of its children until the minheap property is restored. Do we swap it with the left child or the right child? That depends on their values. There's no inherent ordering between the left and right element, but you'll need to take the smaller one in order to maintain the min-heap ordering.

提取最小元素：找到最小堆的最小元素很容易：它总是在顶部。更棘手的部分是如何删除它。（事实上​​，这并没有那么棘手。）首先，我们移除最小元素并将其与堆中的最后一个元素（最底部、最右侧的元素）交换。然后，我们冒泡这个元素，将它与它的一个子元素交换，直到恢复 minheap 属性。我们是用左孩子还是右孩子交换它？这取决于他们的价值观。左右元素之间没有固有的排序，但您需要采用较小的一个以保持最小堆排序。

public class MinHeap {

    private int[] heap;
    private int size;
    private static final int FRONT = 1;

    public MinHeap(int maxSize) {
      heap = new int[maxSize + 1];
      size = 0;
    }

    private int getParent(int position) {
      return position / 2;
    }

    private int getLeftChild(int position) {
      return position * 2;
    }

    private int getRightChild(int position) {
      return position * 2 + 1;
    }

    private void swap(int position1, int position2) {
      int temp = heap[position1];
      heap[position1] = heap[position2];
      heap[position2] = temp;
    }

    private boolean isLeaf(int position) {
      if (position > size / 2) {
        return true;
      }
      return false;
    }

    public void insert(int data) {
      heap[++size] = data;
      int currentItemIndex = size;
      while (heap[currentItemIndex] < heap[getParent(currentItemIndex)]) {
        swap(currentItemIndex, getParent(currentItemIndex));
        currentItemIndex = getParent(currentItemIndex);
      }
    }

    public int delete() {
      int item = heap[FRONT];
      swap(FRONT, size--); // heap[FRONT] = heap[size--];
      heapify(FRONT);
      return item;
    }

    private void heapify(int position) {
      if (isLeaf(position)) {
        return;
      }
      if (heap[position] > heap[getLeftChild(position)]
          || heap[position] > heap[getRightChild(position)]) {
        // if left is smaller than right
        if (heap[getLeftChild(position)] < heap[getRightChild(position)]) {
          // swap with left
          swap(heap[position], heap[getLeftChild(position)]);
          heapify(getLeftChild(position));
        } else {
          // swap with right
          swap(heap[position], heap[getRightChild(position)]);
          heapify(getRightChild(position));
        }
      }
    }

    @Override
    public String toString() {
      StringBuilder output = new StringBuilder();
      for (int i = 1; i <= size / 2; i++) {
        output.append("Parent :" + heap[i]);
        output
            .append("LeftChild : " + heap[getLeftChild(i)] + " RightChild :" + heap[getRightChild(i)])
            .append("\n");
      }
      return output.toString();
    }

    public static void main(String... arg) {
      System.out.println("The Min Heap is ");
      MinHeap minHeap = new MinHeap(15);
      minHeap.insert(5);
      minHeap.insert(3);
      minHeap.insert(17);
      minHeap.insert(10);
      minHeap.insert(84);
      minHeap.insert(19);
      minHeap.insert(6);
      minHeap.insert(22);
      minHeap.insert(9);

      System.out.println(minHeap.toString());
      System.out.println("The Min val is " + minHeap.delete());
    }
  }