c++ - 了解堆(优先级队列)中的向上和向下渗透函数

Question

我在最小堆(顶部最小的键)中向上和向下渗透的代码有一些问题。我最大的提示是这两个代码片段的 for 循环，这导致我无法理解其余代码...

int hole = ++currentSize;
Comparable copy = x;

array[ 0 ] = std::move( copy ); //in the books implementation the zero 
//index is kept empty, is this to create a temporary place for the added element?
for( ; x < array[ hole / 2 ]; hole /= 2 ) //my biggest problem is understanding this for loop!!!
    array[ hole ] = std::move( array[ hole / 2 ] ); //what does this do?
array[ hole ] = std::move( array[ 0 ] );

我不明白这里的for循环。它可能与关系有关，例如第 i 个索引的父项在 i/2 中等等，但我对此一无所知。这是向堆中插入一个元素。感谢任何帮助阐明代码含义的帮助。

然后是 findMin 方法的渗透，我还是不理解它的代码。

/**
    * Internal method to percolate down in the heap.
    * hole is the index at which the percolate begins.
    */
void percolateDown( int hole )
{
    int child;
    Comparable tmp = std::move( array[ hole ] );

    for( ; hole * 2 <= currentSize; hole = child ) //not clear with this for loop!!!
{
    child = hole * 2;
    if( child != currentSize && array[ child + 1 ] < array[ child ] )
    ++child;
    if( array[ child ] < tmp )
    array[ hole ] = std::move( array[ child ] );
    else
        break;
    }
    array[ hole ] = std::move( tmp );
    } //somewhat understood, except the for loop...

主要是for循环，还有那部分代码做了什么？如果问题中有任何业余之处，我们深表歉意。

Answer 1

如你所说:元素的父元素i位于i/2 .代码所做的是插入一个“孔”，这将是放置新元素的地方。 for 循环中的行:

array[ hole ] = std::move( array[ hole / 2 ] );

将父级移动到子级的位置(即“洞”)。所以我们基本上做的是以下内容

while (element being moved up < parent)
    move parent to current index
    current index = index of parent
place element at current index

另一段代码做相反的事情。它有点复杂，因为虽然每个元素只有一个父元素，但它可能有两个子元素。第一个位于 i * 2 ，第二个在 i * 2 + 1 .首先我们检查元素是否有子元素(child != currentSize)。如果 child 较小，我们只想将 parent 与 child 交换。所以我们看看哪个 child 最小(array[ child + 1 ] < array[ child ])。我们将那个 child 与其 parent 进行比较:如果它更小，我们交换它们并继续，否则我们就完成了。最后，我们将要移回的元素放在“洞”中。