0

我一直在尝试编写一个递归 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();
}
 }
4

2 回答 2

4

你的有几个问题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是9and 11，都大于根值。（实际上，您甚至都不打电话heapifyHelper(1)，因为heap[0]它已经比它的两个孩子都小。）

但是通过无条件重复（在存在的孩子身上）单独纠正这一点并不能使你heapify正确。如果你从根到叶子递归，每个值最多可以冒泡一个级别。您必须从叶子递归到根(1)，并且您需要完全筛选值，而不仅仅是一层。

如果您只将一个值与其其中一个子级交换，则每个位置最多被考虑两次。一次将其与其父级进行比较，一次将其与其子级进行比较。当你从根到叶时，当你将一个位置与它的子级进行比较时，它上面的任何位置（甚至没有更小的索引的位置）都不能再改变了。

所以每个值最多可以冒泡一个级别。如果最小元素低于 root 的直接子元素，则 root 不会成为树中的最小元素。如果你从叶子（或者更确切地说是叶子的父母）开始，值可以根据需要冒泡。但是，如果您只将一个值与其较小的孩子交换（如果它小于该值），则每个值仍然只能向下冒泡一个级别，这仍然不需要创建堆。

让我们考虑一下树

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

如果你从根到叶，你交换2和7首先，给

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

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

然后你处理左子树，最后是右子树，产生

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

共。现在底部两层由最小堆组成，但堆属性在上一层被破坏。要再次使其成为堆，1必须进一步筛选（在这种情况下，只有一层）。

如果你从叶子到根，你首先处理右子树，

  6
 / \
4   5

生产

  4
 / \
6   5

为此，然后是左子树

  2
 / \
1   3

生产

  1
 / \
2   3

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

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

然后你会交换7and 1，产生

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

现在根是最小值，但最后一次交换破坏了左子树的堆属性。为了再次使之成为一堆，7必须进一步筛选。

因此，您需要一种siftDown方法（和/或siftUp方法）来根据需要向下（向上）筛选值。

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
}

那么正确的heapify将是

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

这是有效的，因为如果您有一个（二叉树）树，其中两个子树都是最小堆，则筛选根值会构造一个最小堆：

  • 如果根值小于（或等于）它的两个子节点，则整个树已经是一个最小堆。
  • 否则，在根值与其较小的孩子交换之后（不失一般性左边），另一个子树不变，因此仍然是最小堆。并且，由于左孩子是交换前左子树中的最小值，因此根处的值是交换后整个树中的最小值。不过，交换可能已经破坏了左孩子的最小堆属性。但是左右子树并没有改变，所以它们仍然是最小堆。并且新的左子树小于原始树，因此根据归纳假设，筛选其根值会从中创建一个最小堆。所以筛选完成后，我们就有了一个根值最小的树，它的两个子树都是最小堆，也就是最小堆。

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

替代方案，使用siftUp：

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

for 的代码siftUp比 for 短很多siftDown，因为这里只涉及两个节点，不需要检查是否有任何子索引落在数组之外。但是heapify效率较低（见脚注（1））。

siftUp是用于将新值插入堆的方法。所以这个通过将所有值（根值除外）插入现有的最小堆来构建一个堆[当siftUp(index)被调用时，之前的数组部分index已经是一个最小堆]。

注意：你getParentIndex的不正确，

return (childIndex / 2) - 1;

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

return (childIndex - 1) / 2;

(1)实际上，如果您根据需要向上筛选每个值，您可以从根到叶。从叶子的 [parents of the] 到根的 heapify 会更有效。如果你从根到叶，在级别k你有2^k可能需要冒泡k级别的值，这给O(n*log n)构建堆带来了复杂性。如果您从 [parents of the] 叶子向上进行，则您的2^(log n - 1 - k)值可能需要向下冒泡，这给构建堆k带来了复杂性。O(n)

于 2013-02-15T20:42:51.570 回答
0

所以我想我弄清楚了问题所在。

您的 heapify 助手会在您找到一个根小于 leftChild 和 rightChild 的根的那一刻停止。

在运行您的案例时..您会遇到 root (5) 小于 11 和 9 ..但是 11 没有堆积的情况..

解决这个问题的方法很多。我留给你的。

编辑所以 heapify 理想情况下只是将 rootIndex 中的第一个元素放在正确的位置。不创建堆。

如果要创建正确的堆，则需要插入一个新元素并在每次插入时调用 heapify。

于 2013-02-15T20:31:54.513 回答