c++ - theSize/2 是什么意思 percolateDown(i) 函数？

Question

下面代码中的theSize/2是什么意思，这与插入 O(LogN) 有某种关系吗？

template <class Comparable>
void BinaryHeap<Comparable>::buildHeap( )
{
    for( int i = theSize / 2; i > 0; i-- )
        percolateDown( i );
}

对于这个 percolateDown 函数

template <class Comparable>
void BinaryHeap<Comparable>::percolateDown( int hole )
{
  int child;
  Comparable tmp = array[ hole ];

  for( ; hole * 2 <= theSize; hole = child )
  {
    child = hole * 2;
    if( child != theSize && array[child + 1] < array[child])
       child++;
    if( array[ child ] < tmp )
       array[ hole ] = array[ child ];
    else
       break;
  }
  array[ hole ] = tmp;
}

Answer 1

堆的一个非常常见的表示是将它映射到一个数组。在此表示中，对于存储在 a[n] 的任何节点，其子节点位于 a[n*2] 和 a[n*2+1]。根节点位于 a[1]。

鉴于此，将索引除以二(并丢弃任何余数)就是从节点索引到其父节点索引的简单方法。

在 percolateDown 的情况下，想法是从堆的叶子上方一级的节点开始。

尝试搜索“数组中的堆”以获取更多详细信息。