网站设计赏析,沈阳市住房和城乡建设局网站,微小店适合卖做分类网站吗,东莞常平做网站一、堆的定义
堆#xff08;heap#xff09;#xff0c;是⼀棵有着特殊性质的完全⼆叉树#xff0c;可以⽤来实现优先级队列#xff08;priorityqueue#xff09;。 堆需要满⾜以下性质#xff1a; 1. 是⼀棵完全⼆叉树#xff1b; 2. 对于树中每个结点#xff0c;如…一、堆的定义
堆heap是⼀棵有着特殊性质的完全⼆叉树可以⽤来实现优先级队列priorityqueue。 堆需要满⾜以下性质 1. 是⼀棵完全⼆叉树 2. 对于树中每个结点如果存在⼦树那么该结点的权值⼤于等于或⼩于等于⼦树中所有结点 的权值。 如果根结点⼤于等于⼦树结点的权值称为⼤根堆反之称为⼩根堆。
二、堆的存储
由于堆是⼀个完全⼆叉树因此可以⽤⼀个数组来存储。用到的是二叉树的顺序存储
结点下标为i • 如果⽗存在⽗下标为i/2 • 如果左孩⼦存在左孩⼦下标为i × 2 • 如果右孩⼦存在右孩⼦下标为i × 2 1 。 三、核⼼操作
堆中的所有运算⽐如建堆向堆中插⼊元素以及删除元素等都是基于堆中的两个核⼼操作实现的- --向上调整算法以及向下调整算法。 因此在实现堆之前先来掌握两种核⼼操作。 注意以下所有操作都默认堆是⼀个⼤根堆⼩根堆的原理反着来即可。
向上调整算法
算法流程 1. 与⽗结点的权值作⽐较如果⽐它⼤就与⽗亲交换 2. 交换完之后重复1 操作直到⽐⽗亲⼩或者换到根节点的位置。
int n; // 标记堆的⼤⼩
int heap[N]; // 存堆 - 默认是⼀⼤根堆
// 向上调整算法
void up(int child)
{int parent child / 2;// 如果⽗结点存在并且权值⽐⽗结点⼤ while(parent 1 heap[child] heap[parent]){swap(heap[child], heap[parent]);// 交换之后修改下次调整的⽗⼦关系注意顺序不能颠倒 child parent;parent child / 2;}
}
时间复杂度 最差情况需要⾛⼀个树⾼因此时间复杂度为log N
向下调整算法
算法流程 1. 找出左右⼉⼦中权值最⼤的那个如果⽐它⼩就与其交换 2. 交换完之后重复1 操作直到⽐⼉⼦结点的权值都⼤或者换到叶节点的位置。
int n; // 标记堆的⼤⼩
int heap[N]; // 存堆 - 默认是⼀⼤根堆
// 向下调整算法
void down(int parent)
{int child parent * 2;while(child n) // 如果还有孩⼦ {// 找出两个孩⼦谁是最⼤的 if(child 1 n heap[child 1] heap[child]) child;// 最⼤的孩⼦都⽐我⼩说明是⼀个合法的堆 if(heap[child] heap[parent]) return;swap(heap[child], heap[parent]);// 交换之后修改下次调整的⽗⼦关系注意顺序不能颠倒 parent child;child parent * 2;}
}时间复杂度 最差情况需要⾛⼀个树⾼因此时间复杂度为log N 。
四、priority_queue
1、优先级队列
普通的队列是⼀种先进先出的数据结构即元素插⼊在队尾⽽元素删除在队头。 ⽽在优先级队列中元素被赋予优先级当插⼊元素时同样是在队尾但是会根据优先级进⾏位置调整优先级越⾼调整后的位置越靠近队头同样的删除元素也是根据优先级进⾏优先级最⾼的元素队头最先被删除。 其实可以认为优先级队列就是堆实现的⼀个数据结构。 priority_queue就是C提供的已经实现好的优先级队列底层实现就是⼀个堆结构。在算法竞赛中如果是需要使⽤堆的题⽬⼀般就直接⽤现成的priority_queue很少⼿写⼀个堆因为省事~
2、创建priority_queue-初阶
优先级队列的创建结果有很多种因为需要根据实际需求可能会创建出来各种各样的堆 1. 简单内置类型的⼤根堆或⼩根堆⽐如存储int 类型的⼤根堆或⼩根堆 2. 存储字符串的⼤根堆或⼩根堆 3. 存储⾃定义类型的⼤根堆或⼩根堆⽐如堆⾥⾯的数据是⼀个结构体。 关于每⼀种创建结果都需要有与之对应的写法。在初阶阶段先⽤简单的int 类型建堆重点 学习priority_queue的⽤法。
注意 priority_queue 包含在queue 这个头⽂件中。
#include iostream
#include vector
#include queue // 优先级队列的头⽂件在 queue ⾥⾯
using namespace std;
// 优先级队列的使⽤
void test1()
{int a[10] {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};priority_queueint heap; // 默认写法下是⼀个⼤根堆
}
size/empty 1. size 返回元素的个数。 2. empty 返回优先级队列是否为空
push • 往优先级队列⾥⾯添加⼀个元素。 时间复杂度因为底层是⼀个堆结构所以时间复杂度为O(log N) 。 pop • 删除优先级最⾼的元素。 时间复杂度因为底层是⼀个堆结构所以时间复杂度为O(log N) 。 top • 获取优先级最⾼的元素。 时间复杂度O(1) 。
3、创建priority_queue-进阶
以int 类型为例分 别创建⼤根堆和⼩根堆。
#include iostream
#include vector
#include queue // 优先级队列的头⽂件在 queue ⾥⾯
using namespace std;
// 内置类型
void test()
{int a[10] {1, 41, 23, 10, 11, 2, -1, 99, 14, 0};// ⼤根堆 priority_queueint heap1; // 默认就是⼤根堆 // priority_queue数据类型 存数据的结构 数据之间的⽐较⽅式 priority_queueint, vectorint, lessint heap2; // 也是⼤根堆 // ⼩根堆 priority_queueint, vectorint, greaterint heap3; // ⼩根堆 // 测试 for(auto x : a){heap1.push(x);heap2.push(x);heap3.push(x);}while(heap1.size()){cout heap1.top() ; // 获取堆顶元素的值 heap1.pop(); // 删除元素 }cout endl;while(heap2.size()){cout heap2.top() ; // 获取堆顶元素的值 heap2.pop(); // 删除元素 }cout endl;while(heap3.size()){cout heap3.top() ; // 获取堆顶元素的值 heap3.pop(); // 删除元素 }cout endl;
}
int main()
{test();return 0;
}
priority_queue数据类型 存数据的结构 数据之间的⽐较⽅式
greater是小根堆。
