共计 2218 个字符，预计需要花费 6 分钟才能阅读完成。
大家好，我是周一。
明天咱们聊聊堆，以及堆排序。
一、堆
谈到堆，首先咱们要从二叉树说起，从二叉树到齐全二叉树，再才到堆。
1、二叉树
每个结点最多只能有两棵子树，且有左右之分
2、齐全二叉树
一棵深度为 k 的有 n 个结点的二叉树，对树中的结点按从上至下、从左到右的程序进行编号，如果编号为 i（1≤i≤n）的结点与 满二叉树 中（除最初一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树）编号为 i 的结点在二叉树中的地位雷同，则这棵二叉树称为齐全二叉树。
艰深的说法就是：叶子结点只能呈现在最上层和次上层，且最上层的叶子结点集中在树的左部。须要留神的是，满二叉树必定是齐全二叉树，而齐全二叉树不肯定是满二叉树。
对于某个地位为 i 的节点，左孩子（如果有）2i+1，右孩子（如果有）2i+2，父节点(i-1)/2（向下取整）
3、堆
首先是一个齐全二叉树。同时辨别大根堆和小根堆。
大根堆：每一颗子树的最大值都是头节点。
小根堆：每一颗子树的最小值都是头节点。
（1）对于用户顺次输出数字的一个数组，如何将其结构为大根堆？
每插入一个数都和父节点比拟，大于父节点则和父节点替换，直到根节点；如果小于父节点，则马上进行比拟。
// 对于新加进来的 i 地位的数，请放到数组适合地位，使其成为一个大根堆
private void heapInsert(int[] arr, int i) {
// i = 0 或 i 地位数小于父节点
// while 蕴含这两种终止条件
while(arr[i] > arr[(i - 1)/2]) {swap(arr, i, (i - 1)/2);
i = (i - 1)/2;
}
}
（2）获取以后数组最大值，并从堆中删除，同时维持大根堆构造
public int pop() {int ans = heap[0];
swap(heap, 0, --heapSize);
heapify(heap, 0, heapSize);
return ans;
}
// 将 index 地位的数往下沉，直到较大的孩子都没本人大，或者没孩子了
private void heapify(int[] arr, int index, int heapSize) {
// 左子树地位
int left = 2 * index + 1;
while(left < heapSize) {
// 找到左右子树哪个值更大
int maxIndex = (left + 1) < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
// 将左右子树中较大的和父节点比拟
maxIndex = arr[maxIndex] > arr[index] ? maxIndex : index;
// 左右子树较大的值都小于父节点，进行循环
if (maxIndex == index) {break;}
// 将左右子树中较大的和父节点替换
swap(arr, maxIndex, index);
// 以后比拟的节点地位来到较大的子节点
index = maxIndex;
// 从新获取以后节点的左子树
left = 2 * index + 1;
}
}
4、PriorityQueue
底层就是用堆实现的，默认是小根堆
5、工夫复杂度
heapinsert，在曾经是堆构造的数中退出一个数，工夫复杂度是 O(logN)
heapify，在曾经是堆构造的数中退出一个数，工夫复杂度是 O(logN)
二、堆排序
1、将整个数组调整为大根堆，那么此时 0 地位的数就是最大值
2、将 0 地位和数组最大地位的数替换，此时的最大值就处于最初排好序的地位了
3、数组的调整范畴个数减一，循环执行 1、2 步，直到数组为空
public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}
// 将整个数组调整为大根堆，O(NlogN)
for (int i = 0; i < arr.length; i++) {// O(N)
heapinsert(arr, i); // O(logN)
}
// 获取以后数组大小
int heapSize = arr.length;
// 0 地位和数组最大地位的数替换
swap(arr, 0, --heapSize);
while(heapSize > 0) {
// 将替换到 0 地位的数下沉，行将以后数组再次调整为大根堆
heapify(arr, 0, heapSize);
// 0 地位和数组最大地位的数替换
swap(arr, 0, --heapSize);
}
}
4、复杂度
（1）工夫复杂度：O(N*logN)
（2）额定空间复杂度：O(1)
