加压功能不起作用 [英] Heapify function not working
问题描述
我一直在尝试编写一个递归的heapify方法，将整数数组转换成最小堆。主要和堆类别如下所示。 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（无法获取根的父索引）;
}
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};
堆堆=新堆（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] 已经比两者都小它的孩子。）
但是通过无条件重复（对存在的孩子）来纠正它不会使你的 heapify 正确。如果从根到叶再次出现，每个值最多可以起泡一个级别。你必须从叶子复原到根（1），你需要彻底筛选值，而不只是一个级别。
如果您只与一个孩子交换价值，则每个职位最多被认为是两次。一旦比较它的父母，一旦与孩子比较。当你从根到叶子，当你比较一个位置与它的孩子，没有位置上面（没有位置，较小的索引，甚至）可以永远改变。
$ b $所以每个价值都可以在一个最高水平上起泡。如果最小的元素低于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
那么你会交换 7 和 1 ，生成
1
/ \
/ \
7 4
/ \ / \
2 3 6 5
现在根是最小的值，但最后一个交换销毁了左子树的堆属性。要重新生成一个堆， 7 必须进一步删除。
所以你需要一个 siftDown 方法（和/或一个 siftUp 方法），根据需要减少（向上）的值。
private void siftDown（int index）{
int leftChildIndex = getLeftChildIndex（index）;
if（leftChildIndex> = heap.length）{
//叶，不进一步筛选
return;
}
int rightChildIndex = getRightChildIndex（index）;
if（（heap [leftChildIndex]< heap [index]）
&（rightChildIndex> = heap.length || heap [rightChildIndex]> = heap [leftChildIndex]）{
//左边的孩子是最小的，只有小于父
的交换（index，leftChildIndex）;
siftDown（leftChildIndex）;
} else
//不小于父级的小孩，或右边的小孩存在且小于父
if（rightChildIndex< heap.length&& heap [rightChildIndex] heap [index]）{
swap（index，rightChildIndex）;
siftDown（rightChildIndex）;
}
//否则，这个没有更小的孩子，所以不需要更多的筛选
}
然后一个正确的 heapify 将是
public void heapify（）{
//有一个孩子的最后一个索引：
int lastNonLeafIndex = heap.length / 2 - 1; （int index = lastNonLeafIndex; index> = 0; - index）
{
siftDown（index）;
}
}
这是因为如果你有一个（二进制）树其中两个子树都是最小堆，筛选根值构造一个最小堆：
- 如果根值小于（或等于）它的孩子，整个树已经是一个最小堆。
- 否则，在根值与其较小的孩子交换之后（不失一般性）左边），另一个子树不变，因此仍然是一个最小堆。而且，由于左侧子元素是交换之前左侧子树中的最小值，因此根值之后是交换后整个树中的最小值。交换可能已经破坏了左边小孩的最小堆属性。但是左左和右边的子树没有改变，所以它们仍然是最小的堆。而新的左子树小于原始树，因此通过归纳假设，筛选其根值会从中创建一个最小堆。所以在筛选结束后，我们有一个树的最小值在根，两个子树都是最小堆，也就是一个最小堆。
由于每个叶都是一个最小堆，对于 heapify 中处理的每个索引，根据该索引的子树将成为最小堆
另一种方法是使用 siftUp ：
private void siftUp（int index）{
if（index == 0）return; // root，没有办法
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的代码比 siftDown 短得多，因为这里只涉及两个节点，并且不需要检查任何子索引是否落在数组之外。但是 heapify 效率较低（见脚注（1））。
siftUp 是用于将新值插入到堆中的方法。因此，这个通过将所有值（除了根值）插入到现有的最小堆中来构建一个堆[当$ code> siftUp（index）被调用时，数组的一部分
注意：您的 getParentIndex 不正确，
return（childIndex / 2） - 1;
表示索引 1的父母 code> -1 ，索引 3 的父项是 0 正确的是
return（childIndex - 1）/ 2;
（1）实际上，你可以从根到叶如果您根据需要筛选每个值。从[叶子的父母]到根的堆积更有效率。如果你从根到叶子，级别 k 你有 2 ^ k 可能需要泡沫的值up k levels，这给出了构建堆的 O（n * log n）复杂性。如果从[]的父母向上走，你可能需要 2 ^（log n - 1 - k） > k 级别，这给了构建堆的 O（n）的复杂性。
I have been trying to write a recursive heapify method that turns an array of integers into a min-heap. The Main and Heap classes are shown below. Most of the array shown in Main is already a min-heap, but the subtree [11, 4, 5] is not a min-heap. However, the heapify function doesn't seem to reach that subtree. I can't figure out what the problem is, any help would be greatly appreciated.
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();
}
}
There are several problems in your 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];
What if leftChildIndex == heap.length - 1? Then rightChildValue will cause an ArrayIndexOutOfBoundsException.
int rootValue = heap[rootIndex];
if(leftChildValue < rootValue && leftChildValue < rightChildValue) {
swap(rootIndex, leftChildIndex);
heapifyHelper(leftChildIndex);
heapifyHelper(rightChildIndex);
}
else if(rightChildValue < rootValue && rightChildValue < leftChildValue) {
What if both children are equal, and smaller than the parent? In that case you don't swap at all.
swap(rootIndex, rightChildIndex);
heapifyHelper(leftChildIndex);
heapifyHelper(rightChildIndex);
}
}
}
And the reason why the subtree [11, 4, 5] isn't reached is because you only call heapifyHelper for the children if one of the children is smaller than the parent, but when you call heapifyHelper(1), the two children of the node 5 are 9 and 11, both larger than the root value. (Actually, you don't even call heapifyHelper(1), since heap[0]is already smaller than both its children.)
But rectifying that alone by unconditionally recurring (on the children that exist) doesn't make your heapify correct. If you recur from the root to the leaves, each value can bubble up at most one level. You must recur from the leaves to the root(1), and you need to sift the values down completely, not just one level.
If you only swap a value with one of its children, each position is considered at most twice. Once when comparing it to its parent, once when comparing it to its children. When you go from the root to the leaves, when you compare a position to its children, no position above it (no position with a smaller index, even) can ever be changed anymore.
So each value can bubble up at most one level. If the smallest element is below the direct children of root, root won't become the smallest element in the tree. If you start from the leaves (or rather the parents of the leaves), the values can bubble up as far as they need. But if you only swap a value with the smaller of its children (if that is smaller than the value), each value can still only bubble down one level, which still need not create a heap.
Let us consider the tree
7
/ \
/ \
2 6
/ \ / \
1 3 4 5
If you go from the root to the leaves, you swap 2 and 7 first, giving
2
/ \
/ \
7 6
/ \ / \
1 3 4 5
The top two levels are now a min-heap.
Then you treat the left subtree, and finally the right subtree, producing
2
/ \
/ \
1 4
/ \ / \
7 3 6 5
altogether. Now the bottom two levels are composed of min-heaps, but the heap property was destroyed in the level above. To make that a heap again, the 1 must be sifted up further (in this case, just one level).
If you go from the leaves to the root, you first treat the right subtree,
6
/ \
4 5
producing
4
/ \
6 5
for that, then the left subtree
2
/ \
1 3
producing
1
/ \
2 3
there. Both subtrees are now min-heaps. Altogether, you have
7
/ \
/ \
1 4
/ \ / \
2 3 6 5
Then you'd swap 7 and 1, producing
1
/ \
/ \
7 4
/ \ / \
2 3 6 5
Now the root is the smallest value, but the last swap destroyed the heap property of the left subtree. To make that a heap again, the 7 must be sifted down further.
So you need a siftDown method (and/or a siftUp method) that sifts a value down (up) as far as needed.
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
}
Then a correct heapify would be
public void heapify() {
// last index that has a child:
int lastNonLeafIndex = heap.length/2 - 1;
for(int index = lastNonLeafIndex; index >= 0; --index) {
siftDown(index);
}
}
That works because if you have a (binary) tree where both of the subtrees are min-heaps, sifting down the root value constructs a min-heap:
- If the root value is smaller than (or equal to) both its children, the entire tree is already a min-heap.
- Otherwise, after the root value has been swapped with the smaller of its children (without loss of generality the left), the other subtree is unchanged, hence still a min-heap. And, since the left child was the smallest value in the left subtree before the swap, the value at the root is the smallest value in the entire tree after the swap. Swapping may have destroyed the min-heap property of the left child, though. But the left-left and the left-right subtrees have not been changed, so they are still min-heaps. And the new left subtree is smaller than the original tree, so by the induction hypothesis, sifting down its root value creates a min-heap from that. So after sifting down has finished, we have a tree with the smallest value at the root, both of whose subtrees are min-heaps, that is, a min-heap.
Since each leaf is trivially a min-heap, for each index processed in heapify, the subtree rooted at that index becomes a min-heap.
The alternative, using 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);
}
}
The code for siftUp is much shorter than for siftDown, since only two nodes are involved here, and there is no need to check whether any child index falls outside the array. But the heapify is less efficient (see footnote (1)).
siftUp is the method used to insert a new value into a heap. So this one builds a heap by inserting all values (except the root value) into an existing min-heap [when siftUp(index) is called, the part of the array before index is already a min-heap].
Note: your getParentIndex is incorrect,
return (childIndex / 2) - 1;
says the parent of index 1 is -1, and the parent of index 3 is 0, correct is
return (childIndex - 1) / 2;
(1) Actually, you can proceed from the root to the leaves, if you sift each value up as far as needed. It's just more efficient to heapify going from the [parents of the] leaves to the root. If you go from the root to the leaves, at level k you have 2^k values that may need to bubble up k levels, which gives an O(n*log n) complexity for building the heap. If you proceed from the [parents of the] leaves upward, you have 2^(log n - 1 - k) values that may need to bubble down k levels, which gives a complexity of O(n) for building the heap.
这篇关于加压功能不起作用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
