堆的底层实现是完全二叉树:每个节点与其子节点位置相对。父节点总是大于或等于子节点,这种情况下被叫作大顶堆,或者父节点总是小于或等于子节点,这种情况下叫作小顶堆。
注意:给定父节点的子节点不一定按顺序排列。
初始化:
max_heap() 对随机访问迭代器指定的一段元素重新排列,生成一个堆。默认使用的是 < 运算符,可以生成一个大顶堆。
std::vector<double> numbers{2.5,10.0,3.5,6.5,8.0,12.0,1.5,6.0};
std::make_heap(std::begin(numbers), std::end(numbers));
//{12 10 3.5 6.5 8 2.5 1.5 6}
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers), std::greater<>());
//{1.5 6 2.5 6.5 8 12 3.5 10}
添加元素:
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
numbers.push_back(11); // {12 10 3.5 6.5 8 2.5 1.5 6 11}
std::push_heap(std::begin(numbers), std::end(numbers));//{12 11 3.5 10 8 2.5 1.5 6 6.5}
自定义函数添加:
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers), std::greater<>());//{1.5 6 2.5 6.5 8 12 3.5 10}
numbers.push_back(1.2);//{1.5 6 2.5 6.5 8 12 3.5 10 1.2}
std::push_heap(std::begin(numbers), std::end(numbers),std::greater<>());//{1.2 1.5 2.5 6 8 12 3.5 10 6.5}
删除元素:
删除最大元素和添加元素到堆的过程有些相似,但所做的事是相反的。首先调用 pop_heap(),然后从容器中移除最大的元素。
std::vector<double> numbers{2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
std::pop_heap(std::begin(numbers),std::end(numbers));//{10 8 3.5 6.5 6 2.5 1.5 12}
numbers.pop_back();//{10 8 3.5 6.5 6 2.5 1.5}
pop_heap() 函数将第一个元素移到最后,并保证剩下的元素仍然是一个堆。然后就可以使用 vector 的成员函数 pop_back() 移除最后一个元素。
自定义函数删除:
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());//{1.5 6 2.5 6.5 8 12 3.5 10}
std::pop_heap(std::begin(numbers), std::end(numbers),std:: greater<>());//{2.5 6 3.5 6.5 8 12 10 1.5}
numbers.pop_back();//{2.5 6 3.5 6.5 8 12 10}
因为可能会打乱容器中的堆, STL 提供了一个检查序列是否仍然是堆的方法:
if(std::is_heap(std::begin(numbers),std::end(numbers)))
std::cout << "Great! We still have a heap.\n";
else
std::cout << "oh bother! We messed up the heap.\n";
如果元素段是堆,那么 is_heap() 会返回 true。这里是用默认的比较断言 less<> 来检查元素顺序。如果这里使用的是用 greater<> 创建的堆,就会产生错误的结果。
为了得到正确的结果,表达式需要写为:
std::is_heap(std::begin(numbers),std::end(numbers),std::greater<>()
甚至可以更深入地检查元素中是否有部分元素为堆:
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());// {1.5 6 2.5 6.5 8 12 3.5 10}
std::pop_heap (std::begin (numbers),std::end(numbers),std::greater<>());//{2.5 6 3.5 6.5 8 12 10 1.5}
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;
is_heap_until() 函数返回一个迭代器,指向第一个不在堆内的元素。这个代码段会输出最后一个元素的值 1.5,因为在调用 pop_heap() 后,这个元素就不在堆内了。
STL 提供 sort_heap()会将元素段作为堆来排序。如果元素段不是堆,程序会在运行时崩溃。迭代器指向一个假定的大顶堆(用 less<> 排列),然后将堆中的元素排成降序。结果当然不再是大顶堆。
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers), std::end(numbers));//{12 10 3.5 6.5 8 2.5 1.5 6}
std::sort_heap(std::begin(numbers), std::end(numbers));//{1.5 2.5 3.5 6 6.5 8 10 12}
排序操作的结果不是一个大顶堆,而是一个小顶堆。尽管堆并不是全部有序的,但任何全部有序的序列都是堆。
如果用断言 greater() 来创建堆,会生成一个小顶堆,对它进行排序会生成一个降序序列。排序后的序列不是小顶堆。
std::vector<double> numbers {2.5, 10.0, 3.5, 6.5, 8.0, 12.0, 1.5, 6.0};
std::make_heap(std::begin(numbers),std::end(numbers),std::greater<>());// {1.5 6 2.5 6.5 8 12 3.5 10}
std::sort_heap(std::begin(numbers), std::end(numbers),std::greater<>());//{12 10 8 6.5 6 3.5 2.5 1.5}
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <deque>
using std::string;
void show(const std::deque<string>& words, size_t count = 5)
{
if(words.empty()) return;
auto max_len = std::max_element(std::begin(words), std::end(words),
[](const string& s1, const string& s2)
{return s1.size() < s2.size(); })->size();
size_t n {count};
for(const auto& word : words)
{
std::cout << std::setw(max_len + 1) << word << " ";
if(--n) continue;
std::cout << std::endl;
n = count;
}
std::cout << std::endl;
}
int main()
{
std::deque<string> words;
std::string word;
std::cout << "Enter words separated by spaces, enter Ctrl+Z on a separate line to end:\n";
while (true)
{
if ((std::cin >> word).eof())
{
std::cin.clear();
break;
}
words.push_back(word);
}
std::cout << "The words in the list are:" << std::endl;
show(words);
std::make_heap(std::begin(words), std::end(words));
std::cout << "\nAfter making a heap, the words in the list are:" << std::endl;
show(words);
std::cout << "\nYou entered " << words.size() << " words. Enter some more:" << std::endl;
while (true)
{
if ((std::cin >> word).eof())
{
std::cin.clear();
break;
}
words.push_back(word);
std::push_heap(std::begin(words), std::end(words));
}
std::cout << "\nThe words in the list are now:" << std::endl;
show(words);
}
结果显示: