java - Heapify功能不起作用

Question

我一直在尝试编写一个递归的heapify方法，该方法将整数数组变成最小堆。 Main和Heap类如下所示。 Main中显示的大多数数组已经是最小堆，但是子树[11、4、5]不是最小堆。但是，heapify函数似乎未到达该子树。我不知道问题出在哪里，任何帮助将不胜感激。

public class Heap { 
public Heap(int[] array) { 
    heap = array;
}

public void heapify() { 
    heapifyHelper(0);
}

public void heapifyHelper(int rootIndex) { 
    if(isLeafIndex(rootIndex)) { 
        return;
    }

    else { 
        int leftChildIndex = getLeftChildIndex(rootIndex);
        int rightChildIndex = getRightChildIndex(rootIndex);
        int leftChildValue = heap[leftChildIndex];
        int rightChildValue = heap[rightChildIndex];
        int rootValue = heap[rootIndex];

        if(leftChildValue < rootValue && leftChildValue < rightChildValue) { 
            swap(rootIndex, leftChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);
        }

        else if(rightChildValue < rootValue && rightChildValue < leftChildValue) { 
            swap(rootIndex, rightChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);

        }
    }
}

public int getLeftChildIndex(int parentIndex) { 
    return 2 * parentIndex + 1;
}

public int getRightChildIndex(int parentIndex) { 
    return 2 * parentIndex + 2;
}

public int getParentIndex(int childIndex) { 
    if(childIndex == 0) { 
        throw new IllegalArgumentException("Cannot get the parent index of the root.");
    }
    else { 
        return (childIndex / 2) - 1;
    }
}

public boolean isLeafIndex(int index) { 
    int leftIndex = getLeftChildIndex(index);
    int rightIndex = getRightChildIndex(index);
    if(leftIndex >= heap.length && rightIndex >= heap.length) { 
        return true;
    }
    else { 
        return false;
    }
}

public void swap(int index1, int index2) { 
    int temp = heap[index1];
    heap[index1] = heap[index2];
    heap[index2] = temp;
}

public void printHeap() { 
    System.out.println(Arrays.toString(heap));
}
int[] heap;
  }

public class Main { 
public static void main(String[] args) { 
    int[] x = {0, 5, 2, 9, 11, 6, 12, 21, 32, 4, 5};
    Heap heap = new Heap(x);
    heap.printHeap();
    heap.heapify();
    heap.printHeap();
}
 }

Answer 1

您的heapifyHelper中有几个问题：

public void heapifyHelper(int rootIndex) { 
    if(isLeafIndex(rootIndex)) { 
        return;
    }

    else { 
        int leftChildIndex = getLeftChildIndex(rootIndex);
        int rightChildIndex = getRightChildIndex(rootIndex);
        int leftChildValue = heap[leftChildIndex];
        int rightChildValue = heap[rightChildIndex];

如果 leftChildIndex == heap.length - 1怎么办？然后 rightChildValue将导致 ArrayIndexOutOfBoundsException。

        int rootValue = heap[rootIndex];

        if(leftChildValue < rootValue && leftChildValue < rightChildValue) { 
            swap(rootIndex, leftChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);
        }

        else if(rightChildValue < rootValue && rightChildValue < leftChildValue) {

如果两个孩子都是平等的并且比父母小，该怎么办？在这种情况下，您根本不会交换。

            swap(rootIndex, rightChildIndex);
            heapifyHelper(leftChildIndex);
            heapifyHelper(rightChildIndex);

        }
    }
}

不能到达子树 [11, 4, 5]的原因是，如果子节点之一小于父节点，则只为子节点调用 heapifyHelper，而当您调用 heapifyHelper(1)时，节点<的两个子节点< cc>是 5和 9，均大于根值。 （实际上，您甚至都没有呼叫 11，因为 heapifyHelper(1)已经小于其两个子对象。）

但是，仅通过无条件重复（针对存在的子项）来纠正这一点并不能使您的 heap[0]正确。如果从根到叶递归，则每个值最多可以冒充一个级别。您必须从叶子移到根（1），并且需要将值完全向下筛选，而不仅仅是向下筛选。

如果只与一个子项交换一个值，则每个头寸最多被考虑两次。将其与父级进行比较时一次，将其与子级进行比较时一次。当您从根到叶，将位置与其子位置进行比较时，其上方的任何位置（甚至没有索引较小的位置）都无法再更改。

因此，每个值最多可以冒充一个级别。如果最小元素在root的直接子元素之下，则root不会成为树中的最小元素。如果从叶子（或叶子的父对象）开始，则值可以根据需要增大。但是，如果仅用一个较小的子项交换一个值（如果该子项小于该值），则每个值仍然只能冒泡一个级别，而该级别仍不需要创建堆。

让我们考虑一棵树

     7
    / \
   /   \
  2     6
 / \   / \
1   3 4   5

如果从根到叶，先交换 heapify和 2，得到

     2
    / \
   /   \
  7     6
 / \   / \
1   3 4   5

现在，前两个级别是最小堆。

然后处理左子树，最后处理右子树，生成

     2
    / \
   /   \
  1     4
 / \   / \
7   3 6   5

共。现在，最下面的两个级别由最小堆组成，但是在上面的级别中，堆属性被破坏了。要再次创建该堆，必须进一步筛选 7（在这种情况下，仅为一个级别）。

如果您从树叶到根，首先要处理正确的子树，

  6
 / \
4   5

生产

  4
 / \
6   5

为此，然后是左子树

  2
 / \
1   3

生产

  1
 / \
2   3

那里。现在两个子树都是最小堆。总共，你有

     7
    / \
   /   \
  1     4
 / \   / \
2   3 6   5

然后您将 1和 7交换，产生

     1
    / \
   /   \
  7     4
 / \   / \
2   3 6   5

现在，根是最小值，但是最后一次交换破坏了左子树的堆属性。要再次创建该堆，必须进一步过滤 1。

因此，您需要一个 7方法（和/或 siftDown方法），该方法可以根据需要向下（向上）筛选值。

private void siftDown(int index) {
    int leftChildIndex = getLeftChildIndex(index);
    if (leftChildIndex >= heap.length) {
        // a leaf, no further sifting down possible
        return;
    }
    int rightChildIndex = getRightChildIndex(index);
    if ((heap[leftChildIndex] < heap[index])
        && (rightChildIndex >= heap.length || heap[rightChildIndex] >= heap[leftChildIndex)) {
        // left child is smallest or only, and smaller than parent
        swap(index, leftChildIndex);
        siftDown(leftChildIndex);
    } else
        // left child not smaller than parent, or right child exists and is smaller than parent
        if (rightChildIndex < heap.length && heap[rightChildIndex] < heap[index]) {
            swap(index, rightChildIndex);
            siftDown(rightChildIndex);
        }
        // otherwise, this one has no smaller child, so no more sifting needed
}

那么正确的 siftUp将是

public void heapify() {
    // last index that has a child:
    int lastNonLeafIndex = heap.length/2 - 1;
    for(int index = lastNonLeafIndex; index >= 0; --index) {
        siftDown(index);
    }
}

之所以可行，是因为如果您有一个（二进制）树，其中两个子树都是min-heap，则向下筛选根值将构成一个min-heap：


如果根值小于（或等于）其两个子级，则整棵树已经是最小堆。
否则，在根值已与其较小的子级交换后（不失去通用性，左方），另一个子树不变，因此仍然是最小堆。并且，由于左子节点是交换之前左子树中的最小值，因此根节点的值是交换后整个树中的最小值。但是，交换可能会破坏左孩子的min-heap属性。但是左和左和右子树没有更改，因此它们仍然是最小堆。并且新的左子树小于原始树，因此根据归纳假设，对其根值进行筛选会从中产生最小堆。因此，筛选完成后，我们在根处有一棵值最小的树，它们的两个子树都是min堆，即min堆。


由于每个叶子都是最小堆，对于在 heapify中处理的每个索引，以该索引为根的子树将变为最小堆。

替代方法，使用 heapify：

private void siftUp(int index) {
    if (index == 0) return; // root, nothing to do
    int parentIndex = getParentIndex(index); // see Note below
    if (heap[index] < heap[parentIndex]) {
        swap(index, parentIndex);
        siftUp(parentIndex);
    }
}

public void heapify() {
    for(int index = 1; index < heap.length; ++index) {
        siftUp(index);
    }
}

siftUp的代码比 siftUp的代码短得多，因为此处仅涉及两个节点，因此无需检查是否有任何子索引落在数组之外。但是 siftDown的效率较低（请参阅脚注（1））。

heapify是用于将新值插入堆的方法。因此，通过将所有值（根值除外）插入到现有的最小堆中（当调用 siftUp时， siftUp(index)之前的数组部分已经是最小堆），从而构建一个堆。

注意：您的 index不正确，

return (childIndex / 2) - 1;

说索引 getParentIndex的父级是 1，索引 -1的父级是 3，正确的是

return (childIndex - 1) / 2;

（1）实际上，如果根据需要向上筛选每个值，则可以从根到叶。从[叶子的父母]到根，进行堆化只是效率更高。如果从根到叶，则在 0级别具有 k值，可能需要使 2^k级别起泡，这为构建堆增加了 k的复杂性。如果从[父级]树叶开始向上操作，则可能具有 O(n*log n)值，可能需要降低 2^(log n - 1 - k)级别，这为构建堆提供了 k的复杂性。