make_heap()函数如何工作？

Question

我对Vectors和迭代器有基本的了解.但是我在理解下面代码片段的输出方面遇到了问题.

具体来说,我无法找到make_heap()函数的功能.它是如何产出的:91 67 41 24 59 32 23 13 !!

根据我的知识,堆将如下所示:

        91
       /  \
     67    41
    /  \  /  \
   59 24 32  23
  /
 13

所以,我期待输出为:91 67 41 59 24 32 23 13

如果有人能帮助我理解make_heap()如何生成这样的输出,我将非常感激.

int main()
{
int aI[] = { 13, 67, 32, 24, 59, 41, 23, 91 };
vector<int> v(aI, aI + 8);

make_heap( v.begin(), v.end() );

vector<int>::iterator it;
for( it = v.begin(); it != v.end(); ++it )
    cout << *it << " ";
//Output: 91  67  41  24  59  32  23  13

    return 0;
}   

Answer 1

二进制堆必须满足两个约束(另外还有二叉树):

1. shape属性 - 树是一个完整的二叉树(最后一级除外)
2. heap属性:每个节点大于或等于其子节点

堆属性不指定二进制堆中的兄弟节点的顺序,并且单个节点的两个子节点可以自由地互换,除非这样做违反了shape属性.

因此,在您的示例中,您可以在第二级节点之间自由交换,并获得多个合法的输出.