C++教程

堆

请在学习完二叉树后学习堆!

定义

堆是一个比较有序的二叉树,但只有从父节点到子节点之间有序,左右节点是没有顺序的

分类

1.大根堆

即 这个二叉树从父节点到子节点是从大到小的

2.小根堆

即这个二叉树从父节点到子节点是从小到大的

相关函数:

priority_queue优先序列
相关操作:

(p为任意名称)
p.pop();     //弹出顶端的数
p.push();     //插入一个数并且自动排序
p.top();     //读取顶端的数

说明:
优先序列默认是一个大根堆

定义方式:

1.大根堆

priority_queue q;    //简写
priority_queue,less > q;    //全写

2.小根堆

方法一:你可以把数值变成负数,然后用大根堆的方法,读取时再转换回来
方法2:
priority_queue,greater > q;

用处:

1.堆排序
2.快速找第n个最大/小值