堆和優先佇列
堆：
分大頂堆和小頂堆，這里實作的是小頂堆，也就是說父親節點一定小于孩子節點，不像二叉排序樹這樣，堆對子節點之間的大小沒有限制，限制的僅僅只有一個條件，父親一定比孩子節點小，這就是小頂堆，大頂堆則相反
優先佇列：堆中的每個元素都帶有一個優先級，入隊是無序的，出隊是有序的，排序程序只需要在每步插入和洗掉都平衡一下堆就夠了，所以有種排序演算法叫堆排序
代碼實作
結構：
這里用陣列實作,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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71892.html
標籤：其他
上一篇：Dr.VAE
下一篇：按之字形順序列印二叉樹