C++ STL 中的 Heapify？

Question

我正在寻找一个执行 Heapify 的函数，但似乎没有直接来自 C++ STL 的高效函数。

CLRS教材中定义的heapify函数会取入一个元素位置i，假设i的左右子树都是堆，并使以i为根的树成为堆，复杂度为log(n)。

给定 [first, last) 中的堆，我想删除第一个元素，用另一个元素替换它，并维护堆属性。为此，我们只需要调用一次heapify(first)，向下遍历一次堆，复杂度为log(n)。

STL有pop_heap和push_heap函数，首先调用pop_heap和push_heap就可以达到目的，但是pop_heap维护了heap属性，push_heap也维护了heap属性，这就推断在堆中进行了两次遍历。尽管整体复杂度仍然是log(n)，但效率并不高。删除第一个元素后，我们不需要维护堆属性。

除了编写自己的 heapify 函数之外，还有什么好主意吗？

Answer 1

标准库没有swimDownorswimUp函数（如算法书籍中所述，反正std::make_heap在线性时间内实现了向量上的堆化（详细信息请参见此处）。您可以修改所需的元素，然后调用make_heap该向量。

int main()
{
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  // Modify first element
  v[0] = 10;
  std::make_heap(v.begin(),v.end());
  std::cout << "after modification max heap   : " << v.front() << '\n';
}

另一个解决方案是

1. 将修改后的元素推到向量的后面
2. 调用pop_heap它将交换第一个和最后一个元素并重新堆化（单个swimDown）
3. 从后面弹出前第一个元素

这可能会更有效（如果仅针对比较次数）

int main()
{
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  v.push_back(10);
  std::pop_heap(v.begin(), v.end()); // Takes 30 out of the heap and swims 10 down
  v.pop_back(); // Drops 30

  std::cout << "after modification max heap   : " << v.front() << '\n';
}