堆
堆是和队列差不多的一种数据结构，但它有优先级，我们今天来用静态二叉树表示（通过下标控制）：
#include<iostream>
#include<vector>
using namespace std;
template<class T>
struct Less {
booloperator()(const T& L, const T& R)//仿函数
{
returnL > R?true : false;
}
};
template <class T>
struct Great {
booloperator()(const T& L, const T& R)
{
returnL < R?true : false;
}
};
template<class T,class Compare>
class heap {
public:
heap(T*a,size_t n)
{
v.reserve(n);//开辟空间
for(size_t i = 0; i < n; i++)
{
v.push_back(a[i]);
}
for(int i = (n - 2) / 2; i >=0; i--)//不能使用size_t类型，它是无符号整形，减到0之后又会从最大的开始减，用int可以跳出循环
{
size_tnum = v.size();
adjustdown(i,num);
}
}
voidadjustdown(int i,int n)
{
CompareC;
intparent = i;
intchild = i * 2 + 1;
while(child < n)
{
if(child<(n-1)&&C(v[child],v[child + 1]))
{
child++;
}
elseif(C(v[parent],v[child]))
{
swap(v[parent],v[child]);
parent= child;
child= parent * 2 - 1;//继续往下比较
}
else
{
break;
}
}
}
voidadjustup(int i)
{
intchild = i;
intparent = (i - 1) / 2;
Compareco;
while(parent >= 0)
{
if(co(v[parent],v[child]))
{
swap(v[parent],v[child]);
child= parent;
parent= (child - 1) / 2;
}
else
{
break;
}
}
}
voidpop()//删除
{
size_tn = v.size() - 1;
swap(v[0],v[n]);
v.pop_back();
adjustdown(0,n-1);
}
voidpush(const T& x)//插入
{
v.push_back(x);//插入到最后一个位置
size_tn = v.size() - 1;
adjustup(n);//向上调整
}
boolempty()
{
returnv.empty();
}
private:
vector<int>v;
};
int main()
{
inta[] = { 10,13,15,17,19,20,11,14,18,16 };
heap<int,Great<int>> hh(a, sizeof(a) / sizeof(a[0]));//大堆
//heap<int,Less<int>> hh(a, sizeof(a) / sizeof(a[0]));//小堆
hh.push(25);
hh.pop();
return0;
}
大堆（父节点都比子节点大）：
小堆（父节点都比子节点小）：
查看13道真题和解析