c - 堆代码行解释

Question

if (index != indexMaxim)
{
    Rezervare aux = heap.vectorRezervari[index];
    heap.vectorRezervari[index] = heap.vectorRezervari[indexMaxim];
    heap.vectorRezervari[indexMaxim] = aux;

    if (indexMaxim < (heap.nrElements - 1) / 2) // I REALLY DONT GET WHAT THAT MEAN...
        filtrareHeap(heap, indexMaxim);
}

我正在处理堆结构，我认为这一行是将 indexMaxim 的值与父节点进行比较，因此如果该值小于 filtrareHeap() 方法，则调用该方法来交换索引。

你能给我一个更具体的解释吗？

Answer 1

在一个从零开始的数组托管堆中，大小为 n，其中 n > 0 成立，给定任何父节点索引 i使得i在[0,n-1]中，其中n是堆的节点数，对应的子节点可以是发现于:

2 * i + 1
2 * (i + 1)

在这种情况下，上述每一项同样在 [0,n-1]

鉴于此，可以通过获取堆大小并减去 1 来确定真正没有可能的子节点的第一个节点(因此是堆中从该点开始的叶节点)从零开始的索引模型，然后整数除以二。

给定一个大小为 7 的堆，等式得出 3。这是有道理的，因为给定索引

0 1 2 3 4 5 6

我们知道

• 0 是 1,2 的父级
• 1 是 3,4 的父级
• 2 是 5,6 的父级

因此，树中第一个没有子节点的节点是3。您要查询的条件只是确定该节点是否小于该位置，如果是，则进一步行动;否则停止。