实现堆：一次筛选后变得不准确

Question

我目前正在尝试编写一个接受数组并将其放入堆中的程序。我正在尝试实现一个 siftDown 方法，该方法将获取数组的元素并将它们放入堆中，但我只是没有得到我想要的正确输出，我不确定为什么：

public void makeHeap(int[] arr)
{
    for(int i = 0; i <= arr.length; i++)//for each element in the array, we we check its children and sift it down
    {
        siftDown(arr, i);
    }
}

//insert a new root in the correct position. Byu comparing the top element and swapping it with its largest child.
public void siftDown(int[]heap, int i)
{
    int c = i * 2; //grab the children of the current index we are at.

    if(c == 0) // 0*2 is 0 so we make it 1 so it will register the first nodes parents
    {
        c+=1;
    }

   if(c >= heap.length || c+1 >= heap.length) // so we dont go off the end of the array
    {
        return;
    }

    if(heap[c] < heap[c + 1]) //Is child 1 less than child 2? 
    {
        c += 1; //if it is we want c to be the greater child to eventually move upwards
    }

    if(heap[i] < heap[c])//If the parent we have just gotten is smaller than the child defined last loop, then we swap the two. We then call sift down again to compare child and parent.
    {
        heap = swap(heap,i,c);//swap the values
        siftDown(heap, c);//call again to compare the new root with its children.
    }

}

这是我的交换方法：

 public int[] swap(int[]heap, int i, int c)
  {

    //capture the two values in variables
    int ele1 = heap[i];
    int ele2 = heap[c];
    
    heap[i] = ele2;//change heap i to heap c
    heap[c] = ele1;//change heap c to heap i
    
    return heap;
    
  }

起始号码为：4,7,9,6,3,1,5 .我想要得到的输出是 9,7,5,6,3,1,4 但我似乎只能得到 9,7,4,6,3,1,5。似乎一旦 4 在被 9 替换后被筛选一次，该算法就会失控，它认为 3 和 1 是它的 children 而 1,5 应该是。谢谢你或你的帮助！

Answer 1

    int c = i * 2; //grab the children of the current index we are at.

    if(c == 0) // 0*2 is 0 so we make it 1 so it will register the first nodes parents
    {
        c+=1;
    }

我觉得这不对。 children 的堆索引应该是适用于所有情况的通用公式。

Given parentIdx in 0-based array,
leftChildIdx = parentIdx * 2 + 1
rightChildIdx = parentIdx * 2 + 2

这意味着 children 的 0 是 1 和 2，children 的 1 是 3 和 4，children 的 2 是 5 和 6，等等。有效。

您的代码将 1 的 children 放在 2 和 3 上，这显然是错误的。

实现堆：一次筛选后变得不准确

Implementing a heap: becomes inaccurate after one sift

java

arrays

heap