---
# System prepended metadata

title: heapsort
tags: [codebook]

---

---
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;
}
```