c++ - 基于迭代器的自定义 heapify 函数

Question

我正在尝试制作一种适用于我的自定义容器的自定义(而不是使用 STL 方法)堆排序方法。我有迭代器，但是我找不到 make_heap 算法的描述。据我所知，它的作用类似于排列元素，使它们看起来像一个二叉堆，其中每个父节点旁边都有它的两个子节点，但是子节点的子节点呢？具体是怎么安排的？

Answer 1

调用 std::make_heap 后元素的顺序是实现定义的。唯一指定的是最大的元素放在范围内的第一位。

我相信在最常见的实现中，如果一个节点存储在索引 i 中，那么它的左子节点存储在 2*i+1 中，它的右子节点存储在 2*i+1 中2*i+2 的 child 。