堆
这篇文章我们来手写一下堆排序，首先我们来解释一下什么是堆？
堆是一种数据结构，需要满足如下几个特性
- 堆是一颗完全二叉树（生成节点的顺序是从左往右，从上往下依次进行）
- 堆中某个节点值总是不大于或者不小于其父节点的值
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆
大根堆和小根堆如下图所示
假设有如下一个完全二叉树，如何将它调整为一个堆呢？
可以看到10及其子节点符合条件，3及其子节点符合条件，4这个节点不符合条件。
所以要对4这个节点进行调整，调整的过程称为heapify
- 从4这个节点的左右节点找一个大的节点（即10这个节点）和4这个节点进行交换
- 交换完有可能交换后的节点不符合条件，所以还需要进行调整（调整过程和1类似）