**ヒープソート
ヒープソートはバブルソートよりも効率的なソートアルゴリズムであり、数値や他の類似のものをソートすることもできる。これはヒープ（最大または最小）を使用します。ヒープとは2分木のことで、ノードは常にその子ノードよりも大きいか小さいかのどちらかです。各項目は挿入されなければならず、最大でも木の `log_2(n)` レベルを移動することができるので、ヒープを作成するのに`n*log_2(n)` 時間かかる。
それから、ルートノードはすでに最大なので、すぐに取り出してソートされたリストに置くことができる。次に、ルートノードがある場所にリーフノードが置かれ、木が再ソートされる。そしてルートノードが取り出され、再びソートされたリストに置かれる。この処理は木が空になるまで繰り返され、合計で `n*log_2(n)` の時間がかかる。
以下は3つの数字をソートする例である：
```
##########################
# First, build the heap. #
##########################
7 2 9
# Add 7 to root: 
# (7)
2 9
# add two to next leaf node:
# 7
# └── 2
# is it a max heap? Are all child nodes less than their parent nodes? Yes.
9
# add nine to the next leaf node:
# 7
# ├── 2
# └── 9
# Are all child nodes less than their parent nodes? No.
# move nine up:
# 9
# ├── 2
# └── 7
# Are all child nodes less than their parent nodes? Yes.

# No more elements are left. Heap is created. 

###########################
# Now sort from the heap. #
###########################
# take the root node and place it into the list:
# -
# ├── 2
# └── 7
9
# replace the root node with the last leaf node:
# 7
# └── 2
# Are all child nodes less than their parent nodes? Yes.
# take the root node and place it into the list on the left:
# -
# └── 2
7 9
# replace the root node with the last leaf node:
# (2)
# Are all child nodes less than their parent nodes? Yes.
# take the root node and place it into the list on the left: 
# (_)
2 7 9
# the tree is empty, which means we're done sorting!
```

---

**ヒープ化**する

heapifyは、以前のようにヒープを作るときに上向きに調整するのではなく、各ノードを見て、一番右のリーフノードから始めて、ヒープでないものに到達するまで左へ進みます。子ノードがすべて親ノードより小さくないノードに達すると、ルートの値を最大の子ノードと入れ替える。これを、ツリーの一番下に到達するまで、入れ替えた子ノードで繰り返す。そして、ツリー全体のルートに達するまで、この処理を繰り返す。この処理は、すべてのアイテムが毎回木の下に移動する必要がある場合、最大でも `n*log_m(n)` の時間がかかりますが、一般的に木をヒープに変換するのに便利です。
以下は4つの要素を持つ2分木の例である：
```
# start with a non max heap binary tree:
2
├── 9
│   └── 11
└── 7
# 11 is a heap because it has no children, continue to 7
# 7 is a heap because it has no children, continue to 9
# 9 is not a heap, because 11 is greater. Swap.
2
├── 11
│   └── 9
└── 7
# 9 is now a heap. Continue to 2.
# 2 is not a heap. Both 11 and 7 are greater. Swap with 11 since it's highest:
11
├── 2
│   └── 9
└── 7
# 2 is still not a heap. Swap with 9:
11
├── 9
│   └── 2
└── 7
# 2 is a heap, and 11 is the root. We're done!
```
**Heap Sort**
Heap sort is a more efficient sorting algorithm than bubble sort that also sorts numbers or other similarly comparable things. It uses a heap, (can be max or min) which is a binary tree where a node is always greater or lesser than both of its children. It takes `n*log_2(n)` time to create the heap, because each item must be inserted, and can travel up at most `log_2(n)` levels of the tree.
Then, the root node is already max, so it can be taken out and placed in a sorted list instantly. Then, a leaf node is placed where the root node is, and the tree is re-sorted, which takes at most `log_2(n)` time. Then the root node is taken out and placed in the sorted list again. This process is repeated until the tree is empty, which will take a total of `n*log_2(n)` time.
Here's an example sorting 3 numbers:
```
##########################
# First, build the heap. #
##########################
7 2 9
# Add 7 to root: 
# (7)
2 9
# add two to next leaf node:
# 7
# └── 2
# is it a max heap? Are all child nodes less than their parent nodes? Yes.
9
# add nine to the next leaf node:
# 7
# ├── 2
# └── 9
# Are all child nodes less than their parent nodes? No.
# move nine up:
# 9
# ├── 2
# └── 7
# Are all child nodes less than their parent nodes? Yes.

# No more elements are left. Heap is created. 

###########################
# Now sort from the heap. #
###########################
# take the root node and place it into the list:
# -
# ├── 2
# └── 7
9
# replace the root node with the last leaf node:
# 7
# └── 2
# Are all child nodes less than their parent nodes? Yes.
# take the root node and place it into the list on the left:
# -
# └── 2
7 9
# replace the root node with the last leaf node:
# (2)
# Are all child nodes less than their parent nodes? Yes.
# take the root node and place it into the list on the left: 
# (_)
2 7 9
# the tree is empty, which means we're done sorting!
```

---

**Heapify**

Instead of adjusting upwards in heap creation like before, heapify looks at each node, starting with the rightmost leaf node, and goes left until it reaches something that isn't a heap. Once it reaches a node where the children aren't all smaller than the parent, it will switch out the value of the root with the largest child. This is repeated with the swapped child node until it reached the bottom of the tree. Then, this whole process is repeated until the root of the entire tree is reached. This process still takes `n*log_m(n)` time at most, if all items need to move to the bottom of the tree each time, but it's useful for generally transforming trees into heaps.
Here's an example with a binary tree with four elements:
```
# start with a non max heap binary tree:
2
├── 9
│   └── 11
└── 7
# 11 is a heap because it has no children, continue to 7
# 7 is a heap because it has no children, continue to 9
# 9 is not a heap, because 11 is greater. Swap.
2
├── 11
│   └── 9
└── 7
# 9 is now a heap. Continue to 2.
# 2 is not a heap. Both 11 and 7 are greater. Swap with 11 since it's highest:
11
├── 2
│   └── 9
└── 7
# 2 is still not a heap. Swap with 9:
11
├── 9
│   └── 2
└── 7
# 2 is a heap, and 11 is the root. We're done!
```