STLRecipe---heap

创建堆

用来创建堆的函数定义在头文件 algorithm 中。max_heap() 对随机访问迭代器指定的一段元素重新排列，生成一个堆。默认使用的是 < 运算符，可以生成一个大顶堆。例如：

int main()
{
    vector<double>numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
    make_heap(numbers.begin(), numbers.end());
    for(auto i:numbers)
        cout<< i << " ";
}
12 10 3.5 6.5 8 2.5 1.5 6  

image.png

priority_queue 是一个堆。在底层，一个 priority_queue实例创建了一个堆。在堆中，所有成对的连续元素不需要有相同的比较关系。既然如此，为什么 STL 有 priority_queue (它是一个堆)，却还需要创建堆，特别是还需要将堆作为优先级队列？

• 这是因为 priority_queue 可以提供堆没有的优势，它可以自动保持元素的顺序；但我们不能打乱 priority_queue 的有序状态，因为除了第一个元素，我们无法直接访问它的其他元素。如果需要的是一个优先级队列，这一点非常有用。

从另一方面来说，使用 make_heap()创建的堆可以提供一些 priority_queue `没有的优势：

• 可以访问堆中的任意元素，而不限于最大的元素，因为元素被存储在一个容器中，就像是我们自己的 vector。这也提供了偶然破坏元素顺序的可能，但是总可以调用 make_heap() 来还原堆。
• 可以在任何提供随机访问迭代器的序列容器中创建堆。这些序列容器包括普通数组、string 对象、自定义容器。这意味着无论什么时候需要，都可以用这些序列容器的元素创建堆，必要时，可以反复创建。甚至还可以为元素的子集创建堆。

这里有另一个版本的 make_heap()，它有第 3 个参数，可以用来指定一个比较函数用于堆的排序。通过定义一个大于运算符函数，可以生成一个小顶堆。这里可以使用functional中的断言。例如：

int main()
{
    vector<double>numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
    make_heap(begin(numbers), end(numbers),greater<>());
    for(auto i:numbers)
        cout<< i << " ";
}
1.5 6 2.5 6.5 8 12 3.5 10 

可以将模板类型参数指定为greater。这里的这个尖括号为空的版本推断并返回了类型参数。已经有一个用 make_heap()函数在容器中生成的堆。可以在它上面进行很多操作，下面我们来深入了解这些操作。

堆操作

• 堆不是容器，而是组织容器元素的一种特别方式.
• 为了向堆中添加元素，首先可以用任何方法将元素附加到序列中。然后调用 push_heap() 来插入最后一个元素，为了保持堆的结构，这个元素会被重新排列到一个适当的位置。

//push_back() 会在序列末尾添加元素，然后使用 push_heap() 恢复堆的排序。

int main()
{
    vector<double>numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
    make_heap(numbers.begin(), numbers.end());
    numbers.push_back(11);
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    push_heap(begin(numbers),end(numbers));
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
}

12 10 3.5 6.5 8 2.5 1.5 6 11 
12 11 3.5 10 8 2.5 1.5 6 6.5 

• 删除：删除最大元素和添加元素到堆的过程有些相似，但所做的事是相反的。首先调用pop_heap()，然后从容器调用pop_back()移除最大的元素：

int main()
{
    vector<double>numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
    make_heap(numbers.begin(), numbers.end());
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    pop_heap(begin(numbers),end(numbers));
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    numbers.pop_back();
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;    
}

12 10 3.5 6.5 8 2.5 1.5 6 
10 8 3.5 6.5 6 2.5 1.5 12 
10 8 3.5 6.5 6 2.5 1.5 

• 检查序列是否仍然是堆：

cout<<"is heap: " << is_heap(begin(numbers), end(numbers)) << endl;
is heap: 1

注意：创建堆用的什么断言，操作的时候就用同样断言，如greater<>、less<>。

• 更深入地检查元素中是否有部分元素为堆。弹出堆的元素在容器内但是不在堆内，例如：

int main()
{
    vector<double>numbers{2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
    make_heap(numbers.begin(), numbers.end(),greater<>());
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    pop_heap(begin(numbers),end(numbers), greater<>());
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    auto iter = std::is_heap_until(std::begin(numbers),std::end(numbers),std::greater<>());
    if(iter != std::end(numbers))
    std::cout << "numbers is a heap up to "<<*iter <<std::endl;
}

1.5 6 2.5 6.5 8 12 3.5 10 
2.5 6 3.5 6.5 8 12 10 1.5 
numbers is a heap up to 1.5

• 排序：STL 提供的最后一个操作是 sort_heap()，它会将元素段作为堆来排序。

int main()
{
    vector<double>numbers{2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
    make_heap(numbers.begin(), numbers.end(),greater<>());
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
    sort_heap(begin(numbers),end(numbers), greater<>());
    for(auto i:numbers)
        cout<< i << " ";
    cout << endl;
}

1.5 6 2.5 6.5 8 12 3.5 10 
12 10 8 6.5 6 3.5 2.5 1.5 

例子：太长了请参考reference。

参数不需要指定为 `const`，但最好这样做。在任何情况下，比较函数都不能改变传给它的参数值。
    // Find length of longest string
    auto max_len = std::max_element(std::begin(words), std::end(words),
                                  [](const string& s1, const string& s2)
                                  {return s1.size() < s2.size(); })->size();
类似于
bool comp(const T1& a,const T2& b);

---

• reference:http://c.biancheng.net/view/481.html