c++ - make_heap() 函数如何工作？

Question

我对 vector 和迭代器有基本的了解。但是我在理解以下代码片段的输出时遇到了问题。

具体来说，我无法找出 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. 形状属性——树是一棵完全二叉树(除了最后一层)
2. 堆属性:每个节点都大于或等于它的每个子节点

二叉堆中兄弟节点的顺序不是由堆属性指定的，单个节点的两个 child 可以自由互换，除非这样做违反形状属性。

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