---
tags: 資料結構
---
# 資料結構 第九章 堆積結構

雙邊優先佇列(double-ended priority queue)同時支持插入、刪除最大值、刪除最小值

## 一、最小最大堆積 (Min-Max Heaps)
### (一)定義
#### 1、三種特性:
##### (1)為一棵完全二元樹
##### (2)屬於最小層與最大層交錯，Root為最小層
##### (3)假設x為某一棵子樹的樹根
###### a、若x在最小層，則x為該子樹最小值
###### b、若x在最大層，則x為該子樹最大值
#### 2、圖示:
### (二)插入
step1:將要插入的鍵值，插入至完全樹的最後一個位置
step2:向上層(min or max)做比較，調整鍵值位置
【以插入鍵值80與插入鍵值5兩者為例子】
### (三)刪除
step1:刪除最小值(樹根)將完整樹的最後一個位置鍵值，移至樹根。
step2:樹根鍵值向下層(min or max)做比較，調整鍵值位置。
## 二、兩邊堆積(Deaps)
### (一)定義
#### 1、四種特性:
##### (1)樹根不包含鍵值
##### (2)左子樹為最小堆積
##### (3)右子樹為最大堆積
##### (4)調整:
###### a.當右子樹不為空，左子樹的每個點都可以找到，一個對應點在右子樹上，並符合左鍵值＜右鍵值，【對應點＝x+所在高度-1，root高度為1、所在陣列index為0】
###### b.若對應點右子樹不存在，則與對應點的父點做比較。
#### 2、圖示:
### (二)插入
step1:先比較左右子樹的對應點大小
step2:對應點交換完，在個別在左右子樹中調整(最大堆積 & 最小堆積)
【以插入4為例子】
### (三)刪除
step1:先刪除最小值or最大值(左、右子樹root)，並將完整樹最後一個位置的鍵值取代之。
step2:取代完，在個別在左右子樹中調整(最大堆積 & 最小堆積)
【以刪除最小值為例】

## 三、左翼樹 (Leftist Trees)
討論雙邊優先佇列合併所產生
### (一)定義
#### 1、特性:
##### (1)為一棵二元樹，可為空樹。
##### (2)另外部節點到此點的路徑長度為x，每個點皆滿足由 左(x)≧右(x)
#### 2、圖示:
### (二)合併
#### 1、步驟:
step1:比較root大小，選取小的root並保持左子樹的部分
step2:將比較完另一棵樹(root及左子樹)做為step1選取樹的右子樹
step3:其二棵比較的樹的右子樹繼續比較合併
step4:檢查是否滿足特性(2)，為滿足左右子樹做Swap
#### 2、範例圖示:
## 四、二項式堆積(Binomial Heaps)
像左翼樹一樣支援雙邊優先佇列合併。
### (一)成本分攤
時間複雜度與左翼樹些許不同，左翼樹單個操作皆為O(log n)，但二項式堆積單個操作worst為O(n)，但best為O(1)，則平均時間複雜度為O(log n)。
### (二)定義
#### 1、B~k~，k = degree
B~0~、B~1~、B~2~、B~3~
B~0~:為一個點;其餘為下圖
#### 2、k > 0 ，代表一個root，含有B~1~，B~2~，..，B~k~個子樹
#### 3、B~k~ 此樹含有 2^k^個點
#### 4、B~k~ 與 B~k~合併 = B~k+1~

### (三)插入
因為插入令新點為B0插入其他子樹的樹根(最頂層)串列，再將指標指向最小值(原本就次指向最小)故插入點與指標指向的值做比較，較小就更改指標，時間複雜度O(1)。
### (四)合併
#### 1、步驟
故將root做串聯，並將指標指向最小值，故時間複雜度O(1)
#### 2、圖示:
### (五)刪除
#### step1、假設樹為空則回傳error，若不為空執行step2-4
#### step2、指標a指向頂端串列最小值，指標b指向最小值的子點(子點雙向鏈結環串在一起)
#### step3、合併相同的二項式堆積樹值到每個子樹皆唯一
#### step4、再將合併完二像式樹利用指標a指向頂端串列最小值，指標b指向最小值的子點。
【刪除最小值後（為合併）】

### (六)分析

| 操作 | 時間複雜度 | lazy時間複雜度 |
|:-------------- |:-----------------------:|:--------------:|
| 插入 | O(logn) | O(1) |
| 合併 | O(logn) | O(1) |
| 尋找最小值 | O(1) | O(1) |
| 刪除最小值 | O(Max Degree+s)=O(logn) | O(logn) |
| 增加或減少鍵值 | O(logn) | O(logn) |
| 搜尋刪除最大值 | O(n) | O(n) |

lazy:(前提設計)會有指標指向最小值

>參考 : Data Structures in Typescript #17 - Binomial Heap Introduction

## 五、費式堆積(Fibonacci Heaps)
### (一)定義
為二項式堆積的一種特例，除插入、刪除最小、合併(meld)，額外提供decrease key(減少鍵值)、delete(刪除特定(不限最小))

### (二)刪除
從費式堆積a中刪除特定鍵值b，(a頂層鏈結中指向最小值)
#### 1、步驟
##### step1:假設a=b直接刪除最小值,否則執行step2、3
##### step2:從雙向鏈結中刪除b
##### step3:將b所有的子點加入a(頂層)的鏈結中(不用合併)

#### 2、圖示:
### (三)降低鍵值
減少(降低)鍵值，可以減少原本樹的高度
#### 1、步驟
##### step1:減少b的鍵值
##### step2:(前提假設b鍵值小於父點)將b含以下從鏈結中取出，加入頂層串列
##### step3:(前提假設不成立)a將指向b(a頂層鏈結中指向最小值)
#### 2、圖示
### (四)切割(Cascading Cut)
減少鍵值時會改變頂層鏈結，而被拉至頂層的點則為切割
### (五)分析與應用
應用於『最短路徑(單點至所有點的距離)』
#### 費式堆積時間複雜度

| 操作 | 二項式堆積lazy時間複雜度 | 費式堆積時間複雜度 |
|:-------------- |:--------------:|:-----------------------:|
| 插入 | O(1) | O(1) |
| 合併 | O(1) | O(1) |
| 尋找最小值 | O(1) | O(1) |
| 刪除最小值 | O(logn) | O(logn) |
| 增加或減少鍵值 | O(logn) | O(1) |

> 參考資料:Fundamentals of Data Structures in C by Ellis Horowitz, Sartaj Sahni, Susan Anderson-Freed