優(yōu)先隊(duì)列
特殊的隊(duì)列，取出元素的順序是依照元素的優(yōu)先權(quán)(關(guān)鍵字)大小，而不是元素進(jìn)入隊(duì)列的先后順序磅崭。
主要操作
- 插入
- 刪除
然后從這個集合中挑最大，或是最小
數(shù)組實(shí)現(xiàn)
- 插入
- 元素總是插入到尾部 O(1)
- 刪除
- 查找最大(或最小)的元素關(guān)鍵字 O(n)
- 刪除以后瓦哎，需要移動元素砸喻，后面的往前移動 O(n)
鏈表實(shí)現(xiàn)
- 插入
- 元素總是插入到尾部 O(1)
- 刪除
- 查找最大(或最小)的元素關(guān)鍵字 O(n)
- 刪去節(jié)點(diǎn) O(1)
有序數(shù)組
-
插入
- 找到合適的位置 ~O(n) 或是O(log2(n))
- 移動元素并插入 O(n)
-
刪除
- 刪去最后一個元素 ~O(1)
有序鏈表
-
插入
- 找到合適的位置 O(n)
- 插入 O(1)
-
刪除
- 刪除首元素或是尾元素 O(1)
是否使用二叉樹存儲結(jié)構(gòu)？
二叉搜索樹
可能會變成斜樹杭煎。（因?yàn)橛夜?jié)點(diǎn)是最大恩够，刪除一直是右節(jié)點(diǎn)）
如果變成了斜樹，最后其實(shí)和鏈表差不多了羡铲。
堆
結(jié)構(gòu)性：用數(shù)組表示的完全二叉樹
有序性：任一節(jié)點(diǎn)的關(guān)鍵字是其子樹所有節(jié)點(diǎn)的最大值（或最小值）
- “最大堆”蜂桶，“大頂堆”：最大值
- “最小堆”，“小頂堆”：最小值
Paste_Image.png
堆的主要操作集
Heap Create(int MaxSize)
創(chuàng)建一個堆boolean IsFull(Heap H)
判斷是否已經(jīng)滿了boolean IsEmpty(Heap H)
判斷堆是否為空Insert(Heap H,ElementType item)
將元素item插入最大堆HDeleteMax(Heap H)
返回H中最大的元素
以最大堆為例
#結(jié)構(gòu)
struct HeapStruct{
ElementType *element;/*存儲堆得數(shù)組*/
int Size;/*堆得當(dāng)前元素個數(shù)*/
int /*堆得最大容量*/
}
#創(chuàng)建
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("堆已經(jīng)滿了")也切；
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("堆已經(jīng)滿了")；
return;
}
i = ++H->Size;/*堆增大一個雷恃，而且將這個值賦給i*/
for(;item>H->element[i/2] ;){
/*這里疆股，沒有比較i是否大于1 ,因?yàn)樵谠O(shè)計(jì)存儲結(jié)構(gòu)的時候，將H->element[0]中存儲了一個 無窮大倒槐，這樣沒有值會大于這個無窮大旬痹，所以節(jié)省每一輪的一個比較操作*/
H->element[i] = H->element[i/2];
i=i/2;
}
H->Element[i]=item;
}
刪除
刪除圖例：
Paste_Image.png
tips:
必須要注意,最后一個節(jié)點(diǎn)，并不一定是最小的節(jié)點(diǎn)讨越。
#刪除
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;
}
#建立堆
將已經(jīng)存在的N個元素按最大堆得要求存放在一個一維數(shù)組中
方法1：通過插入操作人弓，將N個元素一個個相繼插入到一個初始為空的堆中。
時間代價O(NlogN)
方法2：在線性時間復(fù)雜度下建立最大堆
1.將所有的元素按照輸入順序存入着逐，滿足完全二叉樹的結(jié)構(gòu)特性
2.調(diào)整位置崔赌，滿足最大堆的有序要求
#如何調(diào)整
圖例：
從第一個有子節(jié)點(diǎn)的位置開始：
Paste_Image.png
時間復(fù)雜度：
O(n)
