优先队列
特殊的队列，取出元素的顺序是依照元素的优先权(关键字)大小，而不是元素进入队列的先后顺序。
主要操作
- 插入
- 删除
然后从这个集合中挑最大，或是最小
数组实现
- 插入
- 元素总是插入到尾部 O(1)
- 删除
- 查找最大(或最小)的元素关键字 O(n)
- 删除以后，需要移动元素，后面的往前移动 O(n)
链表实现
- 插入
- 元素总是插入到尾部 O(1)
- 删除
- 查找最大(或最小)的元素关键字 O(n)
- 删去节点 O(1)
有序数组
-
插入
- 找到合适的位置 ~O(n) 或是O(log2(n))
- 移动元素并插入 O(n)
-
删除
- 删去最后一个元素 ~O(1)
有序链表
-
插入
- 找到合适的位置 O(n)
- 插入 O(1)
-
删除
- 删除首元素或是尾元素 O(1)
是否使用二叉树存储结构？
二叉搜索树
可能会变成斜树。（因为右节点是最大，删除一直是右节点）
如果变成了斜树，最后其实和链表差不多了。
堆
结构性：用数组表示的完全二叉树
有序性：任一节点的关键字是其子树所有节点的最大值（或最小值）
- “最大堆”，“大顶堆”：最大值
- “最小堆”，“小顶堆”：最小值
Paste_Image.png
堆的主要操作集
Heap Create(int MaxSize)
创建一个堆boolean IsFull(Heap H)
判断是否已经满了boolean IsEmpty(Heap H)
判断堆是否为空Insert(Heap H,ElementType item)
将元素item插入最大堆HDeleteMax(Heap H)
返回H中最大的元素
以最大堆为例
#结构
struct HeapStruct{
ElementType *element;/*存储堆得数组*/
int Size;/*堆得当前元素个数*/
int /*堆得最大容量*/
}
#创建
Create(int MaxSize){
MaxHeap H = malloc(sizeof(struct HeapStruct));
H->elemnts = malloc( (MaxSize + 1)* sizeof(ElementType));
H->size= 0;
H->element[0]=MaxData ;/*无穷大*/
return H;
}
插入
插入图例：
Paste_Image.png
#插入
void insert(MaxHeap H ,ElementType item){
int i;
if(IsFull(H)){
printf("堆已经满了")；
return;
}
i = ++H->Size;/*堆增大一个，而且将这个值赋给i*/
for(;item>H->element[i/2] && i >1;){
H->element[i] = H->element[i/2];
i=i/2;
}
H->Element[i]=item;
}
void insert(MaxHeap H ,ElementType item){
int i;
if(IsFull(H)){
printf("堆已经满了")；
return;
}
i = ++H->Size;/*堆增大一个，而且将这个值赋给i*/
for(;item>H->element[i/2] ;){
/*这里，没有比较i是否大于1 ,因为在设计存储结构的时候，将H->element[0]中存储了一个 无穷大，这样没有值会大于这个无穷大，所以节省每一轮的一个比较操作*/
H->element[i] = H->element[i/2];
i=i/2;
}
H->Element[i]=item;
}
删除
删除图例：
Paste_Image.png
tips:
必须要注意,最后一个节点，并不一定是最小的节点。
#删除
ElementType DeleteMax(MaxHeap H){
if(IsEmpty(H)){
printf("空堆");
return;
}
ElementType last = H->element[H->size--];
ElementType max = H->element[0];
int Child;
/*这是一棵完全二叉树，所以parent*2<=H->Size 说明有左儿子*/
for(int Parent =1;parent*2 <=H->Size;Praent=Child){
child=parent*2;
//如果child！=H->Size ，说明右儿子存在
if((Child!=H->Size) && (H->element[Child]) < H->element[Child+1]){
Child++;//指向右儿子
}
if(temp>H->element[Child]) break;
else{
H->element[Parent] = H->element[Child];
}
}
H->element[Parent] =last;
return max;
}
#建立堆
将已经存在的N个元素按最大堆得要求存放在一个一维数组中
方法1：通过插入操作，将N个元素一个个相继插入到一个初始为空的堆中。
时间代价O(NlogN)
方法2：在线性时间复杂度下建立最大堆
1.将所有的元素按照输入顺序存入，满足完全二叉树的结构特性
2.调整位置，满足最大堆的有序要求
#如何调整
图例：
从第一个有子节点的位置开始：
Paste_Image.png
时间复杂度：
O(n)
