我一直在尝试编写一个递归的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();
}
}
最佳答案
您的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)时，节点是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的复杂性。