我正在尝试制作一种适用于我的自定义容器的自定义(而不是使用 STL 方法)堆排序方法。我有迭代器,但是我找不到 make_heap 算法的描述。据我所知,它的作用类似于排列元素,使它们看起来像一个二叉堆,其中每个父节点旁边都有它的两个子节点,但是子节点的子节点呢?具体是怎么安排的?
最佳答案
调用 std::make_heap
后元素的顺序是实现定义的。唯一指定的是最大的元素放在范围内的第一位。
我相信在最常见的实现中,如果一个节点存储在索引 i
中,那么它的左子节点存储在 2*i+1
中,它的右子节点存储在 2*i+1
中2*i+2
的 child 。
关于c++ - 基于迭代器的自定义 heapify 函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/22025327/