java - 使用java构建最小堆

Question

我尝试使用 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

我已经调试过了，但还是搞不清楚，有人帮忙吗？非常感谢。

Answer 1

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

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

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());
    }
  }