1、将顺序存储的数据看成是一颗完全二叉树
2、对于大顶堆,确保每棵子树的根节点都是整个子树中的最大值;这就保证了根节点是所有数据中的最大值,但不保证所有数据有序。
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200310223017806.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcxNTI4Nw==,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200504131430395.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcxNTI4Nw==,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/2020050413151236.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcxNTI4Nw==,size_16,color_FFFFFF,t_70)
![在这里插入图片描述](https://img-blog.csdnimg.cn/20200504131600615.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjcxNTI4Nw==,size_16,color_FFFFFF,t_70)
#include<iostream>
using namespace std;
void heapAdjust(int data[], int start, int end)
{
int tmp = data[start];
for (size_t i = start*2; i <= end; i*=2)
{
if (i < end && data[i]<data[i+1])
{
++i;
}
if (tmp>=data[i])
{
break;
}
data[start] = data[i];
start = i;
}
data[start] = tmp;
}
void heapSort(int data[], int start, int end)
{
for (size_t i = end/2; i > 0; i--)
{
heapAdjust(data, i, end);
}
for (size_t i = end; i > 1; i--)
{
swap(data[1], data[i]);
heapAdjust(data, 1, i-1);
}
}
int main()
{
int b[9] = { -1,49,38,65,97,76,13,27,49 };
for (size_t i = 1; i < 9; i++)
{
cout << b[i] << " ";
}
cout << endl;
heapSort(b, 1, 8);
for (size_t i = 1; i < 9; i++)
{
cout << b[i] << " ";
}
cout << endl;
int a[11] = {-1, 7,3,2,6,9,1,2,0,6,4 };
for (size_t i = 1; i < 11; i++)
{
cout << a[i] << " ";
}
cout << endl;
heapSort(a, 1, 10);
for (size_t i = 1; i < 11; i++)
{
cout << a[i] << " ";
}
cout << endl;
return 0;
}
STL中优先队列的应用
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
struct PosType
{
int row;
int col;
};
bool operator<(const PosType a, const PosType b)
{
return a.row < b.row;
}
bool operator>(const PosType a, const PosType b)
{
return a.row > b.row;
}
class cmp
{
public:
bool operator()(const PosType a, const PosType b)const
{
return a.row > b.row;
}
};
void test1()
{
PosType p[] = { {3, 4}, {5, 6}, {4, 1} }, q;
priority_queue<PosType, deque<PosType>, cmp> pri_queue;
for (int i = 0; i < 3; i++)
pri_queue.push(p[i]);
cout << "优先队列元素数=" << pri_queue.size() << endl;
while (!pri_queue.empty())
{
q = pri_queue.top();
cout << '(' << q.row << ", " << q.col << ") ";
pri_queue.pop();
}
cout << endl;
}
void test2()
{
PosType p[] = { {3, 4}, {5, 6}, {4, 1} }, q;
priority_queue<PosType, vector<PosType>, greater<PosType>> pri_queue;
for (int i = 0; i < 3; i++)
pri_queue.push(p[i]);
cout << "优先队列元素数=" << pri_queue.size() << endl;
while (!pri_queue.empty())
{
q = pri_queue.top();
cout << '(' << q.row << ", " << q.col << ") ";
pri_queue.pop();
}
cout << endl;
}
void test3()
{
int p[] = { 3,5,4 },q;
priority_queue<int, vector<int>, less<int>> pri_queue;
for (int i = 0; i < 3; i++)
pri_queue.push(p[i]);
cout << "优先队列元素数=" << pri_queue.size() << endl;
while (!pri_queue.empty())
{
q = pri_queue.top();
cout << q<<" ";
pri_queue.pop();
}
cout << endl;
}
int main()
{
test1();
test2();
test3();
return 0;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)