数据结构--二叉堆与优先队列

堆的一些性质

1、堆是一颗完全二叉树

2、堆的顶端一定是“最大”/最小”的，但是要注意一个点，这里的大和小并不是传统意义下的大和小，它是相对于优先级而言的.

3.堆一般有两种样子，小根堆和大根堆，分别对应第二个性质中的“堆顶最大”“堆顶最小”，对于大根堆而言，任何一个非根节点，它的优先级都小于堆顶，对于小根堆而言，任何一个非根节点，它的优先级都大于堆顶

4、操作：

插入一个元素

取得最小（最大）的数值，并且删除
　　
　　能够完成这种操作的数据结构叫做优先队列

而能够使用二叉树，完成这种操作的数据结构叫做堆（二叉堆）

5、堆与优先队列的时间复杂度：

若共有n个元素，则可在O（logn）的时间内完成上述两种操作

优先队列

STL中的优先队列就是采用大根堆来实现的。

//优先队列需要头文件 
#include<queue> 
// 定义优先队列 
priority_queue<结构类型> 队列名; 
priority_queue <int> q; 
priority_queue <double> d; 
//优先队列的操作 
q.size();//返回q里元素个数 
q.empty();//返回q是否为空，空则返回1，否则返回0 
q.push(k);//在q的末尾插入k 
q.pop();//删掉q的第一个元素 
q.top();//返回q的第一个元素
1
2
3
4
5
6
7
8
9
10
11
12

例1：合并果子

less和greater优先队列

priority_queue <int,vector<int>,less<int> > p; 
priority_queue <int,vector<int>,greater<int> > q;
1
2

less从大到小， greater是从小到大

结构体优先队列

要想使用结构体的优先队列， 需要在结构体内部重载小于号

struct node 
{ 
  int x,y; 
  bool operator < (const node & a) const 
 { 
    return x<a.x; 
 } 
};
1
2
3
4
5
6
7
8

一个node 结构体有两个成员，x 和y ，它的小于规则是 x小者小。
它也是按照重载后的小于规则，从大到小排序的。

priority_queue <node> q;
int main()
{
  k.x = 10, k.y = 100; q.push(k);
  k.x = 12, k.y = 60; q.push(k);
  k.x = 14, k.y = 40; q.push(k);
  k.x = 6, k.y = 80; q.push(k);
  k.x = 8, k.y = 20; q.push(k);
  while (!q.empty())
 {
    node m = q.top(); q.pop();
    printf("(%d,%d) ", m.x, m.y);
 }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

程序大意就是插入 这五个node,再来看看它的输出：
(14,40) (12,60) (10,100) (8,20) (6,80)
就是按照 x从大到小排序的.
例题2：最高的奖励

课后练习

1、卡车加油
2、小b浇花