java - 从基于固定大小数组的 MinHeap 数据结构中删除任何元素

Question

我在 java 中使用 array based MinHeap。我正在尝试创建一个自定义方法，它不仅可以从堆中删除 root 但不能删除任何元素。下面是 MinHeap 代码-

public class MinHeap {

    /** Fixed-size array based heap representation */
    private int[] h;
    /** Number of nodes in the heap (h) */
    private int n = 0;

    /** Constructs a heap of specified size */
    public MinHeap(final int size) {
        h = new int[size];
    }

    /** Returns (without removing) the smallest (min) element from the heap. */
    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Heap is empty!");
        }

        return h[0];
    }

    /** Removes and returns the smallest (min) element from the heap. */
    public int poll() {
        if (isEmpty()) {
            throw new RuntimeException("Heap is empty!");
        }

        final int min = h[0];
        h[0] = h[n - 1];
        if (--n > 0)
            siftDown(0);
        return min;
    }

    /** Checks if the heap is empty. */
    public boolean isEmpty() {
        return n == 0;
    }

    /** Adds a new element to the heap and sifts up/down accordingly. */
    public void add(final int value) {
        if (n == h.length) {
            throw new RuntimeException("Heap is full!");
        }

        h[n] = value;
        siftUp(n);
        n++;
    }

    /**
     * Sift up to make sure the heap property is not broken. This method is used
     * when a new element is added to the heap and we need to make sure that it
     * is at the right spot.
     */
    private void siftUp(final int index) {
        if (index > 0) {
            final int parent = (index - 1) / 2;
            if (h[parent] > h[index]) {
                swap(parent, index);
                siftUp(parent);
            }
        }
    }

    /**
     * Sift down to make sure that the heap property is not broken This method
     * is used when removing the min element, and we need to make sure that the
     * replacing element is at the right spot.
     */
    private void siftDown(int index) {

        final int leftChild = 2 * index + 1;
        final int rightChild = 2 * index + 2;

        // Check if the children are outside the h bounds.
        if (rightChild >= n && leftChild >= n)
            return;

        // Determine the smallest child out of the left and right children.
        final int smallestChild = h[rightChild] > h[leftChild] ? leftChild
                : rightChild;

        if (h[index] > h[smallestChild]) {
            swap(smallestChild, index);
            siftDown(smallestChild);
        }
    }

    /** Helper method for swapping h elements */
    private void swap(int a, int b) {
        int temp = h[a];
        h[a] = h[b];
        h[b] = temp;
    }

/** Returns the size of heap. */    
    public int size() {
        return n;
    }

}

我如何设计一个方法来从这个 MinHeap 中删除任何元素？

Answer 1

如果知道要删除的元素的索引，

private void removeAt(int where) {
    // This should never happen, you should ensure to call it only with valid indices
    if (n == 0) throw new IllegalArgumentException("Trying to delete from empty heap");
    if (where >= n) throw new IllegalArgumentException("Informative error message");

    // Now for the working cases
    if (where == n-1) {
        // removing the final leaf, trivial
        --n;
        return;
    }
    // other nodes
    // place last leaf into place where deletion occurs
    h[where] = h[n-1];
    // take note that we have now one element less
    --n;
    // the new node here can be smaller than the previous,
    // so it might be smaller than the parent, therefore sift up
    // if that is the case
    if (where > 0 && h[where] > h[(where-1)/2]) {
        siftUp(where);
    } else if (where < n/2) {
        // Now, if where has a child, the new value could be larger
        // than that of the child, therefore sift down
        siftDown(where);
    }
}

移除指定值(如果存在)的公开函数将是

public void remove(int value) {
    for(int i = 0; i < n; ++i) {
        if (h[i] == value) {
            removeAt(i);
            // assumes that only one value should be removed,
            // even if duplicates are in the heap, otherwise
            // replace the break with --i to continue removing
            break;
        }
    }
}

总而言之，我们可以通过用最后一个叶子的值替换值来删除给定位置的节点(在删除不是微不足道的情况下)，然后从删除位置向上或向下筛选。 (只需要进行一次筛选或不需要筛选，具体取决于与父项和/或子项(如果存在)的比较。)

这是可行的，因为堆不变量满足删除位置上方和下方树的部分，因此如果交换放置在那里的新值小于父级，向上筛选会将其放置在上方的适当位置删除位置。移动的所有元素都小于子元素中的任何元素，因此为删除位置下方(包括)的部分保持堆不变性。如果新值大于直接子项之一，则基本上是从位于删除位置顶部的子堆中删除根，因此 siftDown 恢复堆不变性。

siftDown 方法中提到的缺陷的修复是将 smallestChild 设置为 leftChild if rightChild >= n:

final int smallestChild = (rightChild >= n || h[rightChild] > h[leftChild]) ? leftChild
            : rightChild;