---
tags: codebook
---
{%hackmd theme-dark %}
# heapsort
堆積排序
## 概念
1. 製作最大堆
2. 持續維護堆的性質，並將最大值逐個推到陣列末端
## 範例
0. 初始堆
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
9 -> {8 7}
7->{6 3}
8->{5 4}
5->{2 0}
4->{1}
}
```
1. 將根和最後一個葉對換，並刪除最後一個葉
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
1[color=turquoise]
1-> {8 7}
7->{6 3}
8->{5 4}
5->{2 0}
4->{9[color=turquoise;style=dashed]}
}
```
```arr:[9]```
2. 維護堆性質，1和8換
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
8[color=red]
8-> {1[color=red] 7}
7->{6 3}
1->{5 4}
5->{2 0}
}
```
```arr:[9]```
3. 維護堆性質，1和5換
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
8-> {5[color=red] 7}
7->{6 3}
5->{1[color=red] 4}
1->{2 0}
}
```
```arr:[9]```
4. 維護堆性質，1和2換
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
8-> {5 7}
7->{6 3}
5->{2[color=red] 4}
2->{1[color=red] 0}
}
```
```arr:[9]```
5~. 再次重複步驟1直到堆大小為0
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
0[color=turquoise]
0-> {5 7}
7->{6 3}
5->{2 4}
2->{1 8[color=turquoise;style=dashed]}
}
```
```arr:[8|9]```
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
0[color=red;label=7]
0-> {5 7[color=red;label=0]}
7->{6 3}
5->{2 4}
2->1
}
```
```arr:[8|9]```
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
7
7-> {5 6[color=red]}
6->{0[color=red] 3}
5->{2 4}
2->1
}
```
```arr:[8|9]```
```graphviz
digraph heap{
node[fontcolor = white;color=white]
edge[color=white]
bgcolor = "#343434"
1[color=turquoise]
1-> {5 6}
6->{0 3}
5->{2 4}
2->{7[color=turquoise;style=dashed]}
}
```
```arr:[7|8|9]```
以下類推
## 範例程式碼
```cpp=
#include<iostream>
#include<vector>
using namespace std;
void heapify(vector<int>& v, size_t size, size_t cur) {
size_t maxpos = cur, left = (cur << 1) + 1, right = (cur << 1) + 2;
if (left < size && v[left] > v[maxpos])
maxpos = left;
if (right < size && v[right] > v[maxpos])
maxpos = right;
if (maxpos != cur)
swap(v[cur], v[maxpos]), heapify(v, size, maxpos);
}
void heapsort(vector<int>& v) {
for (size_t i = v.size() / 2; i; i--)
heapify(v, v.size(), i - 1);
for (size_t i = v.size(); i; i--)
swap(v[0], v[i - 1]), heapify(v, i - 1, 0);
}
int main() {
vector<int> v{1, 5, 4, 2, 0, 3, 6, 7, 8, 9};
heapsort(v);
for (const auto& i : v)
cout << i << ' ';
return 0;
}
```
Sign in with Wallet
Connect another wallet