Min-Max Heap - HackMD
文章推薦指數： 80 %
Insertion - 插入 · 此時Node 2 你不知道他是否符合Min-Max Heap 的定義，所以我們要與他的Parent Node 1 比較 · 根據定義3 ，Root = Node 1 = Min Level，相當於此顆Tree 是 ...
Published
LinkedwithGitHub
Like3
Bookmark
Subscribe
---
title:'Min-MaxHeap'
disqus:hackmd
---
[TOC]
##Min-MaxHeap
>[color=#34d2db]**Def：**
>1.是CompleteBinaryTree
>2.Level依序由Min/MaxHeap交互出現
>3.Root在MinLevel
>4.某Nodex在MinLevel，代表以x為Root的Tree中，x是最小值
>(同理MaxLevel)
*此樹就是由MinHeap與MaxHeap互相交疊形成
*再次提醒，定義3有提到Root必須為MinLevel的值
---
###Insertion-插入
*依照CompleteBinaryTree性質，插入Node2
*此時Node2你不知道他是否符合Min-MaxHeap的定義，所以我們要與他的ParentNode1比較
*根據定義3，Root=Node1=MinLevel，相當於此顆Tree是MinHeap
所以當Node2
*所以當我們從某Max/MinLevelNode往Grandchild的級距(也就是index*2)持續下去，相當於在搜尋一顆Max/MinHeap
*當然這兩顆"分裂"出來的Tree不完全稱得上是一顆完整的Max/MinHeap
但是它仍然保留了Max/MinHeap最重要的特性，就是Parent與Child的關係
*千萬別忘了Parent與Child的關係是這樣
*回過頭，我們從Min-MaxHeap移除了RootData
*那麼第二小的Data莫過於在下一層裡的其中一個Node
*而我們把這個Level放回去Min-MaxHeap來觀察，不就是Root的Grandchild！
所以我們將"優先"搜尋Root的Grandchild
---
*使用以下Tree演示
```graphviz
graphgraphname{
1[label="7"]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="9"]
6[label="10"]
7[label="45"]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
*移除RootData：7
```graphviz
graphgraphname{
1[label=""]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="9"]
6[label="10"]
7[label="45"]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
*儲存LastNodeData至x
```graphviz
graphgraphname{
1[label=""]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="9"]
6[label="10"]
7[label="45"]
45[label="x=45"shape=sstyle=dashed]
1--2
1--3
2--4
2--5
3--6
3--7
}
```
*移除LastNode
```graphviz
graphgraphname{
1[label=""]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="9"]
6[label="10"]
45[label="x=45"shape=sstyle=dashed]
1--2
1--3
2--4
2--5
3--6
}
```
*將x放入RootData
```graphviz
graphgraphname{
1[label="45"]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="9"]
6[label="10"]
1--2
1--3
2--4
2--5
3--6
}
```
*使用case2
```graphviz
graphgraphname{
1[label="45"color=red]
2[label="70"]
3[label="40"]
4[label="30"color=blue]
5[label="9"color=blue]
6[label="10"color=blue]
1--2
1--3
2--4
2--5
3--6
}
```
*交換完成，且符合Min-MaxHeap定義
```graphviz
graphgraphname{
1[label="9"]
2[label="70"]
3[label="40"]
4[label="30"]
5[label="45"color=red]
6[label="10"]
1--2
1--3
2--4
2--5
3--6
}
```
---
:::danger
**if(爸爸可能不知情)**
:::
*以上述例子來說，更新完Tree之後雖然MinLevel中的Node符合定義了
但切記
---
**Case3：含飴弄不到孫-Root無合適Grandchild**
*考慮以下情況，進行刪除
```graphviz
graphgraphname{
1[label="1"]
2[label="100"]
3[label="2"]
4[label="90"]
5[label="10"]
1--2
1--3
2--4
2--5
}
```
*我們發現10的Grandchild是符合定義的，不須更動
```graphviz
graphgraphname{
1[label="10"]
2[label="100"]
3[label="2"]
4[label="90"color=red]
1--2
1--3
2--4
}
```
*但是10的Child卻不符合定義(因為Parent已經換人了)
```graphviz
graphgraphname{
1[label="10"]
2[label="100"]
3[label="2(嘿嘿)"color=blue]
4[label="90"]
1--2
1--3
2--4
}
```
*所以當沒有與Grandchild互動時，還是要記得檢查Child
```graphviz
graphgraphname{
1[label="2"color=blue]
2[label="100"]
3[label="10"]
4[label="90"]
1--2
1--3
2--4
}
```
>[color=#]其實Case2,3是差不多的，不論是Parent或Child更換，都要再去拜訪彼此是否符合定義
:::warning
**TimeComplexity：**$O(log_2n)$
:::
---
##Deap
>[color=#d62234]**Def：**
>1.本身是CompleteBinaryTree
>1.Root不存Data
>2.Root的LeftSubtree(左子樹)為Min-Heap
>3.Root的RightSubtree(右子樹)為Max-Heap
>4.假設兩顆子樹各自的Node編號(Index)排列方式一樣，
>則在相同編號下：左子樹的Data$\leq$右子樹的Data
*左子樹的6號=33$\leq$右子樹的6號=60
*填上編號觀看很容易，但在程式裡若要比較兩Index，這兩個對稱的Index相對於整棵Tree來說彼此有甚麼關係
***Def：樹起始Level1**
我們知道每層的LevelNode最大值=$2^{k-1},k=Level$
*想像每一層LevelNodes都是上一層LevelNodes數量"複製"兩次而來
*上一層的數量若為1個單位(2個Nodes)，下一層的數量就是2個單位
而左右Heap中Node彼此的間距就是1單位
*一個單位=上一層的最大Nodes=$2^{k-2}$
*所以只要將某個Index±$2^{k-2}$，就可以找到隔壁相同位置的Node，(加往右，減往左)
*$Tree[4]=10\leqTree[4+2^{3-2}]=Tree[6]=70$
---
###Insertion-插入
*根據CompleteBinaryTree特性插入至第n+1的位置(n=Nodes)
則插入的Node不是在Min-Heap就是在Max-Heap
*分為兩種Case
1.插入Min-Heap
*比較對應Max-Heap位置的父節點
2.插入Max-Heap
*比較對應Min-Heap位置的節點
交換完之後在做Insertion(Heapify)
---
###Deletion-刪除
*我們可以選擇做最小(綠Node)或是最大(紅Node)刪除，
```graphviz
graphgraphname{
1[label=""]
2[label="1"color=green]
3[label="100"color=red]
4[label="10"]
5[label="7"]
6[label="70"]
7[label="88"]
8[label="13"]
9[label="22"]
10[label="33"]
11[label="60"]
12[label="33"]
13[label="22"]
14[label="60"]
15[label="55"]
1--2
1--3
2--4
2--5
3--6
3--7
4--8
4--9
5--10
5--11
6--12
6--13
7--14
7--15
}
```
####MinimalDeletion-最小刪除
*依照Min-HeapDeletion的步驟，將Root值替換成LastNode值、並刪除LastNode
```graphviz
graphgraphname{
1[label=""]
2[label="55"color=green]
3[label="100"]
4[label="10"]
5[label="7"]
6[label="70"]
7[label="88"]
8[label="13"]
9[label="22"]
10[label="33"]
11[label="60"]
12[label="33"]
13[label="22"]
14[label="60"]
1--2
1--3
2--4
2--5
3--6
3--7
4--8
4--9
5--10
5--11
6--12
6--13
7--14
}
```
*確認完Child關係後，記得要在判斷與右子樹相對位Node的關係
```graphviz
graphgraphname{
1[label=""]
2[label="7"]
3[label="100"]
4[label="10"]
5[label="33"]
6[label="70"]
7[label="88"]
8[label="13"]
9[label="22"]
10[label="55"color=green]
11[label="60"]
12[label="33"color=red]
13[label="22"]
14[label="60"]
1--2
1--3
2--4
2--5
3--6
3--7
4--8
4--9
5--10
5--11
6--12
6--13
7--14
}
```
*
```graphviz
graphgraphname{
1[label=""]
2[label="7"]
3[label="100"]
4[label="10"]
5[label="33"]
6[label="70"]
7[label="88"]
8[label="13"]
9[label="22"]
10[label="33"]
11[label="60"]
12[label="55"color=green]
13[label="22"]
14[label="60"]
1--2
1--3
2--4
2--5
3--6
3--7
4--8
4--9
5--10
5--11
6--12
6--13
7--14
}
```
######tags:`DataStructure`
3
×
Signin
Email
Password
Forgotpassword
or
Byclickingbelow,youagreetoourtermsofservice.
SigninviaFacebook
SigninviaTwitter
SigninviaGitHub
SigninviaDropbox
SigninviaGoogle
NewtoHackMD?Signup
延伸文章資訊
- 1heap
Heap. 定義：堆積分成Min heap與Max heap兩種。Min heap必須具備. 的條件：. (1) 是一棵complete binary tree。 (2) 是一棵min tree...
- 2[資料結構] 堆積(Heap) - iT 邦幫忙
堆積(Heap)，是一種特殊的完全二元樹，而堆疊不一樣，是完全不同的概念。 有分兩種，一種是最小堆積，另一種是最大堆積。 最小堆積. 如下圖，完全二元樹所有的父節點都 ...
- 3資料結構大便當： Binary Heap
如果是max-heap 的話，每個node 都要比自己child 大，如果是min-heap 反之（下圖是max-heap）; （max-heap）root 就會是整個heap 的最大值. （m...
- 4[演算法] 堆積排序法(Heap Sort)
二元樹的一種 ⇒ 每個父節點最多兩個子節點 · 堆積樹為完全二元樹(Complete Binary Tree)的一種 · 最小堆積(Min Heap) ：父節點的值小於子節點. 樹根(root)...
- 5Min-Max Heap - HackMD
Insertion - 插入 · 此時Node 2 你不知道他是否符合Min-Max Heap 的定義，所以我們要與他的Parent Node 1 比較 · 根據定義3 ，Root = Node...
