Min堆Java实现

Question

我已经实现了一个min堆，并在寻找一个更简单的解决方案。

有人为这个问题提出更简单的解决方案吗？

谢谢。

import com.sun.org.apache.xalan.internal.xsltc.dom.MultiValuedNodeHeapIterator;

import java.util.Arrays;

public class MinHeap {

    private int capacity = 10;
    private int size = 0;

    int[] items = new int[capacity];

    private int getLeftChildIndex(int parentIndex) { return 2 * parentIndex + 1 ;}
    private int getRightChildIndex(int parentIndex) { return 2 * parentIndex + 2 ;}
    private int getParentIndex(int childIndex) { return (childIndex -1) / 2 ;}

    private boolean hasLeftChild(int index) { return getLeftChildIndex(index) < size; }
    private boolean hasRightChild(int index) { return getRightChildIndex(index) < size; }
    private boolean hasParent(int index) { return getParentIndex(index) >= 0; }

    private int  leftChild(int index) { return items[getLeftChildIndex(index)]; }
    private int  rightChild(int index) { return items[getRightChildIndex(index)]; }
    private int  parent(int index) { return items[getParentIndex(index)]; }


    private void swap(int indexOne, int indexTwo){
        int temp = items[indexOne];
        items[indexOne] = items[indexTwo];
        items[indexTwo] = temp;
    }

    private void ensureExtraCapacity() {
        if (size == capacity) {
            items = Arrays.copyOf(items, capacity * 2);
            capacity *= 2;
        }
    }

    private int peek() {
        if (size == 0) throw new IllegalStateException();
        return items[0];
    }

    private int poll() {
        if (size == 0) throw new IllegalStateException();
        int item = items[0];
        items[0] = items[size - 1];
        size--;
        heapifyDown();
        return item;
    }

    public void add(int item) {
        ensureExtraCapacity();
        items[size] = item;
        size++;
        heapifyUp();
    }

    public void heapifyUp() {
        int index = size - 1;
        while ( hasParent(index) && parent(index) > items[index] ) {
            swap (getParentIndex(index),index);
            index = getParentIndex(index);
        }
    }

    public void heapifyDown() {
        int index = 0;
        while ( hasLeftChild(index) ) {
            int smallerChildIndex = getLeftChildIndex(index);
            if (hasRightChild(index) && rightChild(index) < leftChild(index)) {
                smallerChildIndex = getRightChildIndex(index);
            }

            if (items[index] < items[smallerChildIndex]) {
                break;
            } else {
                swap(index, smallerChildIndex);
            }
            index = smallerChildIndex;
        }
    }


}

Answer 1

我对你的代码有一个建议。

1. 创建一个方法来检查当前大小是否无效，并重用它(MinHeap#peek和MinHeap#poll方法)。

private void assertCurrentSizeIsValid() {
   if (size == 0) {
      throw new IllegalStateException();
   }
}