目录
这三个函数位于
这是该函数的官方定义:
这个函数用于建立堆。
前两个参数为迭代器类型,最后一个为仿函数,用于确定建堆方式。
默认使用大堆排序。
可以调用官方仿函数greater
使用方式如下:
- int main()
- {
- vector<int> arr = { 20, 43, 21, 1, 6, 30 };
- make_heap(arr.begin(), arr.end());//默认大堆
- cout << arr.front();//输出堆顶
- return 0;
- }
官方定义:
这个用于将堆底数据加入堆结构中。
因为make_heap只能建堆,如果当前堆数据发生改变,就需要使用push_heap重回大堆/小堆。
值得注意:first 到 last-1 之间的元素必须满足堆结构。它仅仅是将last之前元素插入堆中。
意思就是,如果一次性插入多个元素,它只会把最后一个元素(堆底)加入堆结构中。
其参数与make_heap相同,不再赘述。
使用方式如下:
- int main()
- {
- vector<int> arr = { 20, 43, 21, 1, 6, 30 };
- make_heap(arr.begin(), arr.end());
- arr.push_back(99);
- arr.push_back(79);
- push_heap(arr.begin(), arr.end());
- cout << "此时堆顶:" << arr.front() << endl;
- return 0;
- }
可以发现,99并没有成为堆顶元素,因为79才是最后一个插入的数据,99被“忽视”了,使用时要格外注意。
官方定义:
该函数作用是“删除”堆顶元素。
为什么加引号——因为就像堆排序那样,所谓删除只是将堆顶元素移至堆底。
其实就是把first元素与last上一个元素交换位置。因为默认last指向堆底的下一个位置(空位置),就像vector的end()一样。
当然其参数与push_heap相同,不再赘述。
使用方式如下:
- int main()
- {
- vector<int> arr = { 20, 43, 21, 1, 6, 30 };
- make_heap(arr.begin(), arr.end());//建大堆
- cout << "原堆顶:" << arr.front() << endl;
- pop_heap(arr.begin(), arr.end());
- cout << "此时堆顶:" << arr.front() << endl;
- cout << "此时堆底:" << arr.back();
- return 0;
- }
官方定义:
该函数就是堆排序。
但前提是该结构在调用sort_heap前已经是堆结构。
sort_heap内部只是把堆顶放堆底,然后再排堆,再取堆顶到新堆底,...直到排完。
同样,参数不再赘述,与之前一致。
重点还是使用:
- int main()
- {
- vector<int> arr = { 20, 43, 21, 1, 6, 30 };
- make_heap(arr.begin(), arr.end());//确保排序前已是堆结构
- sort_heap(arr.begin(), arr.end());
- for (auto n : arr)
- cout << n << " ";
- return 0;
- }
- //错误代码
- int main()
- {
- vector<int> arr = { 20, 43, 21, 1, 6, 30 };
- //排序前不是堆结构
- sort_heap(arr.begin(), arr.end());
- for (auto n : arr)
- cout << n << " ";
- return 0;
- }
直接报错。
如有错误,敬请斧正