code前端网STL算法之堆排序：底层是数组，又保持二叉树特性
上图中，紫色代表数组中元素的踪迹。可以看出，每个节点的值都大于其左右子节点。左右儿童没有尺寸要求。连通性并不指定同一棵树中节点之间的关系范围。这是最高级别。同时，这里可以注意的是，如果是一个大堆，那么底座一定是树中最大的。同样，如果是一个小堆，那么根一定是树中最小的节点。
分类方案中堆结构较低，但STL中没有直接提供堆结构。而是将堆相关的算法写在算法中。我不会在这里过多地介绍捆绑包的模拟和实现。今天我要讲的是如何使用STL中提供的堆算法。
堆算法
在STL中，提供了多种堆算法。
★make_heap
★push_heap
★pop_heap
★sort_heap
这里给出第一个使用算法的例子‽♿♿上面的代码使用了第一个数组建筑 获取向量，然后在vec vec上构建堆，提取构建的向量的第一个元素，对其进行排序，然后进行堆排序，最后打印结果。输出结果如下：
读完堆算法基本使用。现在，让我们看看这些界面是如何在STL中呈现的。
1。 make_heap
前面说过，分为主堆和小堆。我们在创建堆的时候需要指定堆，但是在前面的例子中我们没有指定堆的大小。 STL规定，如果不指定，默认是大栈结构。从上面两组make_heap接口可以看出，第一组是默认的，没有提供定义堆大小的接口，而这里实现了第二组。我们可以在函子的结构体中实现这里传递的参数。
对于给定的例子，我们现在可以解释另一个问题，为什么我们在进行堆排序时需要先构建一个向量？因为堆的主要实现是数组的形式，而向量是对堆数组的高层封装，所以这些库中的容器集提供了很多接口和迭代器，使用起来方便很多。 make_heap提供的接口中，前两个是所有类型的迭代器（当然这里也可以直接传递数组指针）。无论是make_heap还是其他三个函数，这里的服务器空间总是左边关闭，右边打开。 ，这是需要注意的事情。
接下来我们在这里介绍函子的实现。还是上面的例子，我们如何让顶部成为最小的一堆呢？
<span style="font-family:'楷体', '楷体_GB2312', SimKai;font-size:18px;">//仿函数结构：</span><span style="font-family:sans-serif;"><br><br>struct Compare<br>{<br><span style="line-height:0px;"></span><span style="line-height:0px;"></span> bool operator()(int num1, int num2)<br> {<br> return num1 > num2;<br> }<span style="line-height:0px;"></span><span style="line-height:0px;"></span><br>};</span><br>//构建堆栈时，参数shift改为
<span style="font-size:18px;font-family:'楷体', '楷体_GB2312', SimKai;">make_heap(vec.begin(), vec.end() , Compare()); // 建小堆<br></span
<span style="font-size:18px;font-family:'楷体', '楷体_GB2312', SimKai;">make_heap(vec.begin(), vec.end() , Compare()); // 建小堆<br></span注意，我上面写的是num1 > num2，所以这样构建的顶点是小堆栈。这是针对 make_heap 的。
2。 push_heap 和 pop_heap
push 的意思是向向量中插入一个元素，但这里不是直接插入元素。事实上，他的工作只是进行调整。在push_heap之前，需要先调用vec .push_back(x)，在向量的末尾添加一个元素，然后调用push_heap函数进行调整，使树再次整体符合堆结构。
pop_heap 与push_heap 相同。它无法直接更改向量中元素的数量。对于堆来说，pop 所做的就是丢弃向量的第一个元素。为了避免直接破坏树结构，首先调用pop_heap函数将堆中的最大值或最小值放在向量的末尾。同时，进行调整，使堆结构仍然可用，然后调用 vec.pop+back() 函数从向量中删除最后一个元素。
这就是添加和删除的整个过程。
3。 sort_heap
顾名思义，sort_heap就是排序的意思。对堆栈结构进行排序会导致向量的元素被排序。这里，当形成大堆时，排序结果按升序排列，而当形成小堆时，排序结果按降序排列。
以上就是bundle类型的基本算法。关于C++11中新引入的两个函数，这里不再讨论。
关于STL中的栈结构，这里有几点需要注意：
1。因为堆系统是一个基于向量的系统，所以如果要做堆排序，整个过程中必须至少构建一次堆（make_heap）。
2。构建完成后，如果再次向向量中插入元素，则需要调用push_heap(v1.begin(), v1.end())进行向上调整；如果从向量中弹出一个元素，则需要调用 pop_heap(v1.begin(), v1.end()) 进行向下调整。
如果不修正，调用sort_heap(v1.begin(), v1.end())函数时，会因为非法堆而出现断言错误。
3。你不能允许尾部向量被多次加载，然后生成多次，这会在排序时造成混乱和优化错误。当然，重复插入或删除后，可以重建堆，但时间成本会很高。
堆栈结构的实际应用
接下来看调查题：
CVTE：统计公司员工想吃的高K水果
如果你具备了以上基础，我就给出现场演示在这里
#include <algorithm>
#include <map>
#include <string>
#include <vector>
struct Min
{
bool operator()(pair<string, int> p1, pair<string, int> p2)
{
return p1.second > p2.second;
}
};
void HeapSort()
{
vector<string> v1 = { "苹果", "香蕉", "苹果"
, "苹果", "苹果", "香蕉"
, "苹果", "猕猴桃", "草莓" };
map<string, int> fruit;
//用map统计次数
for (size_t i = 0; i < v1.size(); i++)
{
fruit[v1[i]]++;
}
// 用heap排序
vector<pair<string, int>> vec;
map<string, int>::iterator it = fruit.begin();
//while (it != fruit.end())
//{
// vec.push_back(pair<string, int>(it->first, it->second));
// it++;
//}
vec.insert(vec.begin(), fruit.begin(), fruit.end());
make_heap(vec.begin(), vec.end(), Min());
sort_heap(vec.begin(), vec.end(), Min());
int K = 3;
for (size_t i = 0; (i < K) && (i < vec.size()); i++)
{
cout << vec[i].first <<"--"<<vec[i].second<< endl;
}
}
int main()
{
HeapSort();
system("pause");
return 0;
}堆排序是数据结构中非常重要的一部分。在实际开发中，最好了解STL中给出的算法，如上所述。如果你刚刚入门，建议对系统和算法的基本实现有更深入的了解。堆校正算法无疑是数据结构的重要组成部分。接下来我们将模拟桩结构并更深入地了解底层结构。
来自：“木慧”博客
链接：http://muhuizz.blog.51cto.com/11321490/1879003
版权声明
本文仅代表作者观点，不代表Code前端网立场。
本文系作者Code前端网发表，如需转载，请注明页面地址。
