堆在C ++ STL中？ [英] Heapify in C++ STL?

问题描述

我正在寻找一个可以进行Heapify的功能，但是似乎没有直接来自C ++ STL的有效功能。

I am looking for a function that does Heapify but seems that there is no efficient function directly from C++ STL.

CLRS教科书中定义的heapify函数将进入元素位置i，假设i的左右子树都是堆，并使树成为根

A heapify function as defined in CLRS text book will take in an element location i, assuming the left and right sub trees of i are both heaps, and make the tree rooted at i become a heap, and complexity is log(n).

在[first，last）中给出一个堆，我想删除第一个元素，将其替换与另一个元素，并保持堆属性。为此，我们只需要调用一次heapify（first），一次遍历堆，复杂度为log（n）。

Given a heap in [first, last), I would like to remove the first element, replace it with another element, and maintain the heap property. To achieve this, we only need to call heapify(first) once, traverse down the heap once, with log(n) complexity.

STL具有pop_heap和push_heap函数，可以通过首先调用pop_heap和push_heap来实现目标，但是pop_heap维护堆属性，而push_heap也维护堆属性，这推断出两个在堆中遍历。即使总体复杂度仍然是log（n），它也不是很有效。

STL has pop_heap and push_heap functions, and it could achieve the goal by first call pop_heap and push_heap, but pop_heap maintains heap property, and push_heap also maintains heap property, this infers two traverse in the heap. Even though the overall complexity is still log(n), it is not efficient. We do not need to maintain the heap property after removing the first element.

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

Any good idea besides writing my own heapify function?

推荐答案

标准库没有 swimDown 或 swimUp 函数（如算法书籍中所述，无论如何 std :: make_heap 可以在向量上实现heapify在线性时间内（详细信息此处）。您可以修改所需的元素，然后调用向量上的 make_heap 。

The standard library has no swimDown or swimUp functions (as described in algorithms books, anyway std::make_heap achieves heapify on a vector in linear time (details here). You can modify the element you want and then call make_heap on the vector.

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. 从后面弹出先前的第一个元素

1. Push the modified element to the back of the vector
2. Call pop_heap which will exchange the first and the last elements and reheapify (a single swimDown)
3. Pop the former first element from the back

这可能会更有效（如果只是用于比较次数）

This might probably be even more efficient (if only for the number of comparisons) needed

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';
}

这篇关于堆在C ++ STL中？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！