c - C 中的 Downheap 实现

Question

我有DownheapC 语言的源代码，它将在不违反堆属性的情况下向下移动元素（每个节点的值大于/小于或等于其父节点的值，最小/最大值元素位于root.) 在树的任何节点上。

downheap(int k)
{
    int temp, i;
    temp = a[k];
    while(k <= N/2)
    {
        i = 2*k;
        if(i < N && a[i] < a[i+1]) i++;
        if(temp > a[i]) break;
        a[k] = a[i]; k = i;
    }
    a[k] = temp;
}

N是数组的节点总数a。我质疑这个程序是否可以从左到右下移节点以保持完全二叉树的属性？如何证明它，因为不存在右节点必须小于/大于左节点的属性。

标签： calgorithmdata-structures

Answer 1

downheap(int k) // k is the index of the item in the heap 
{
  int temp, i;
  temp = a[k]; // Use temp to store the item
  while (k <= N / 2) // Make sure that we don't get outside of the heap boundaries
  {
    i = 2 * k; // Helper line to be used as an index for the children of the node
    if (i < N && a[i] < a[i + 1]) i++; // check which of the children is 
    // Bigger to exchange with the item
    if (temp > a[i]) break; // Item already in-place
    a[k] = a[i];
    k = i; // Exchange item with the children we found to be the biggest
  }
  a[k] = temp; // Put the item in its correct position
}

希望点赞有用