堆和优先队列
堆：
分大顶堆和小顶堆，这里实现的是小顶堆，也就是说父亲节点一定小于孩子节点，不像二叉排序树这样，堆对子节点之间的大小没有限制，限制的仅仅只有一个条件，父亲一定比孩子节点小，这就是小顶堆，大顶堆则相反
优先队列：堆中的每个元素都带有一个优先级，入队是无序的，出队是有序的，排序过程只需要在每步插入和删除都平衡一下堆就够了，所以有种排序算法叫堆排序
代码实现
结构：
这里用数组实现,length代表堆数组的长度，注意这里的树形结构是完全二叉树结构
int Heap[MAX]={0};
int length = 0;
寻找父亲和孩子节点
这里反回的是节点的索引
int parent(int j){
if(j>0){
return (j-1)/2; //返回当前节点父亲的位置
}
return -1; //返回当前节点父亲的位置
}
int left(int j){
return j*2+1;
}
int right(int j){
return j*2+2;
}
元素上浮
上浮操作发生在插入的时候，因为插入永远都是从尾部插入，为了平衡堆，所以需要将插入的元素 上浮到符合小顶堆的位置
//上浮
void up(int j){
if(j>0 && Heap[j]<Heap[parent(j)]){ //如果比父母小
swap(Heap[j],Heap[parent(j)]);// 交换
up(parent(j)); //递归
}
}
元素下沉
下沉操作发生在删除元素的时候，因为删除元素的逻辑是将堆顶元素和尾部元素替换，注意，堆顶元素永远都是整个堆的最小的元素
那为什么要和尾部元素替换呢？为了方便堆顶元素的移除，尾部元素移除很方便快速
将尾部元素替换到堆顶后，可能会打破平衡，所以需要将刚替换的堆顶元素下沉
//下沉
void down(int j){
//堆是一颗完全二叉树 先有左边 再有右边
if(has_left(j)){
int small = left(j);
if(has_right(j))
if(Heap[small]>Heap[right(j)])
small = right(j);
if(Heap[small]<Heap[j]){
swap(Heap[small],Heap[j]);
down(small); //递归
}
}
}
添加和删除
//添加
void add(int val){
Heap[length++] = val;
up(length-1); //将新元素上浮
}
//删除 取堆顶元素
int remove(){
swap(Heap[0],Heap[length-1]);//先和最后一个换 再删除
int r = Heap[--length]; //返回结果
down(0); //堆顶下沉
return r;
}
取最小值
int get_min(){
if(length>0){
return Heap[0];
}else{
return -1;
}
}
所有可执行代码
#include <iostream>
using namespace std;
#define MAX 100
int Heap[MAX]={0};
int length = 0;
int parent(int j){
if(j>0){
return (j-1)/2; //返回当前节点父亲的位置
}
return -1; //返回当前节点父亲的位置
}
int left(int j){
return j*2+1;
}
int right(int j){
return j*2+2;
}
bool has_left(int j){
return left(j)<length;
}
bool has_right(int j){
return right(j)<length;
}
//上浮
void up(int j){
if(j>0 && Heap[j]<Heap[parent(j)]){ //如果比父母小
swap(Heap[j],Heap[parent(j)]);// 交换
up(parent(j)); //递归
}
}
//下沉
void down(int j){
//堆是一颗完全二叉树 先有左边 再有右边
if(has_left(j)){
int small = left(j);
if(has_right(j))
if(Heap[small]>Heap[right(j)])
small = right(j);
if(Heap[small]<Heap[j]){
swap(Heap[small],Heap[j]);
down(small); //递归
}
}
}
int get_min(){
if(length>0){
return Heap[0];
}else{
return -1;
}
}
//添加
void add(int val){
Heap[length++] = val;
up(length-1); //将新元素上浮
}
//删除 取堆顶元素
int remove(){
swap(Heap[0],Heap[length-1]);//先和最后一个换 再删除
int r = Heap[--length]; //返回结果
down(0); //堆顶下沉
return r;
}
int main(int argc, char *argv[])
{
add(43);
add(53);
add(4);
add(3);
add(9);
add(100);
cout<<remove()<<endl;
cout<<remove()<<endl;
cout<<remove()<<endl;
cout<<remove()<<endl;
cout<<remove()<<endl;
cout<<remove()<<endl;
cout<<"----------"<<endl;
return 0;
}