2

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

具体来说，我无法找出 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;
}
4

3 回答 3

7

二叉堆必须满足两个约束（除了作为二叉树之外）：

  1. shape 属性——树是完全二叉树（最后一层除外）
  2. 堆属性：每个节点都大于或等于它的每个子节点

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

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

于 2013-06-27T07:48:10.857 回答
3

通过对元素重新排序以使它们满足堆约束，在向量中make_heap构造一个二叉堆。构造的堆是一个最大堆，也就是说，它将最大的（根据operator<或提供的比较）元素放在第一个元素中，即堆的根，它是向量的第一个元素。

二叉堆是一棵平衡二叉树，满足父节点的值总是比子节点的值大（在这种情况下，更常见的情况下，更小）的条件。这意味着根总是包含最大的元素。结合对根的有效提取，这构成了一个很好的优先级队列。

二叉堆以广度优先的顺序存储在数组中。也就是说，根在位置 0，它是位置 1 和 2 的直接子代，位置 3 和 4 是 1 的子代，位置 5 和 6 是 2 的子代，依此类推。通常，节点的子节点n位于2*n + 1和2*n + 2。

在 C++ 中，该函数与向量make_heap一起实现了一个完整的优先级队列。还有一个容器包装器将它们组合在一个类中。push_heappop_heappriority_queue

优先级队列主要用于著名的 Dijkstra 算法和各种调度算法。因为 Dijkstra 的算法需要选择最小值，所以更常见的是在根中定义具有最小值的堆。C++ 标准库选择使用最大值来定义它，但请注意，您可以通过提供它greater_than而不是less_than比较器来轻松获得最小堆。

建立堆有两种方法。通过将每个元素推向它，或者通过固定前半部分元素的不变量（后半部分是叶子）。后者效率更高，因此：

  1. [ 13、67、32、24、59、41、23、91 ] _ _
    • 24 < 91
  2. [ 13、67、32、91、59、41、23、24 ] _ _ _ _
    • 32 < 41
  3. [ 13、67、41、91、59、32、23、24 ] _ _ _ _
    • 67 < 91
  4. [ 13、91、41、67、59、32、23、24 ] _ _ _ _
    • 13 < 91
  5. [ 91、13、41、67、59、32、23、24 ] _ _ _ _
    • 向下移动的元素可能仍然违反约束，这次它确实：13 < 67
  6. [ 91、67、41、13、59、32、23、24 ] _ _
    • 并且仍然违反约束：13 < 24
  7. [91、67、41、24、59、32、23、13]
    • 根处理，我们完成了
于 2013-06-27T07:29:09.427 回答
3

当堆积一个未排序的数组时，该算法利用了一半数组将是叶节点（数组中较高的索引）而另一半将是这些叶节点的父节点的优势。该算法只需要遍历父节点并修复它们的逻辑子树。叶节点一开始是有效的子堆，因为根据定义它们大于它们不存在的子节点。

所以我们只需要修复至少有一个非叶节点的子堆。以正确的顺序完成（从数组中间到最低索引），当最后一个父节点被堆化时，整个数组将是一个有效堆。

每个步骤如下所示：

iteration 1:

    13 67 32 24 59 41 23 91
              ^              current parent under consideration
                          ^  children of this parent

    13 67 32 91 59 41 23 24  after heapifying this sub-tree
             --          --


iteration 2:

    13 67 32 91 59 41 23 24
           ^                 current parent under consideration
                    ^  ^     children of this parent

    13 67 41 91 59 32 23 24  after heapifying this sub-tree
          --       -- 


iteration 3:

    13 67 41 91 59 32 23 24
        ^                    current parent under consideration
              ^  ^           children of this parent

    13 91 41 67 59 32 23 24  after heapifying this sub-tree
       --    --

iteration 4:

    13 91 41 67 59 32 23 24
     ^                       current parent under consideration
        ^  ^                 children of this parent

    91 13 41 67 59 32 23 24  heapify swap 1
    -- --
    91 67 41 13 59 32 23 24  heapify swap 2
       --    --
    91 67 41 24 59 32 23 13  after heapifying this sub-tree
             --          --

堆积数组的简单方法是从索引遍历数组0，n-1并在每次迭代时将该索引处的元素“添加”到由该索引之前的元素组成的堆中。这将导致您期望的堆。该算法导致nheapify 操作。make_heap()结果在n/2heapify 操作中使用的算法。它会产生一个不同但仍然有效的堆。

于 2013-06-27T08:56:42.500 回答