最小优先级支持的操作:
1.INSERT(S,x):将元素x插入队列S
2.MINIMUM(S):返回S中最小的元素
3.EXTRACT_MIN(S):去掉并返回S中最小的元素
4.DECREASE_KEY(S,x,key):将下标为x的元素值降低为key
使用最小堆实现最小优先级队列。最小堆是一个完全二叉树,从编号1开始:
注意几个操作:向下调整(建堆、调整堆),向上调整(建堆后,插入元素、更改元素)、heap_size的应用和变化
//最小优先级队列
#include<stdio.h>
#include<stdlib.h>
int heap_size = 0;
int parent(int i){
return i/2;
}
int left_child(int i){
return 2*i;
}
int right_child(int i){
return 2*i+1;
}
void swap(int * a, int * b){