下面代码中的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;
}
最佳答案
堆的一个非常常见的表示是将它映射到一个数组。在此表示中,对于存储在 a[n]
的任何节点,其子节点位于 a[n*2]
和 a[n*2+1]
。根节点位于 a[1]
。
鉴于此,将索引除以二(并丢弃任何余数)就是从节点索引到其父节点索引的简单方法。
在 percolateDown
的情况下,想法是从堆的叶子上方一级的节点开始。
尝试搜索“数组中的堆”以获取更多详细信息。
关于c++ - theSize/2 是什么意思 percolateDown(i) 函数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34910122/