数据结构中的堆是什么？
性质
- 堆是一个完全二叉树
- 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”，对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”
实现
完全二叉树适合用数据存储，一是可以节约空间，二是通过数组下标可以找到一个节点的左右子节点和父节点。
假设节点的坐标为 x，那么左子节点的坐标就是 x*2，右子节点的下标为 x*2+1，父节点的下标为x/2。
插入操作
新插入的元素放在堆的后面，接着调整新元素的位置，最后满足堆的特征，调整的过程叫作堆化。
堆化有两种，从下往上和从上往下。自下往上，就是顺着节点所在路径，然后对比节点和父节点的大小关系，如果不满足子节点小于等于父节点的大小关系，就互换两个节点。直到父子节点之间满足大小关系。
代码示例：
import java.util.Arrays; public class SimpleHeap { // 数组，从下标1开始存储数组 private int[] a; // 堆可以存储的最大数据个数 private int n; // 堆中已经存储的数据个数 private int count; public SimpleHeap(int capacity) { a = new int[capacity + 1]; n = capacity; count = 0; } /** * 插入新元素 * * @param value 新元素 */ public void insert(int value) { if (count >= n) { return; } ++count; a[count] = value; int p = count; while ((p >> 1) > 0 && a[p >> 1] < a[p]) { int temp = a[p]; a[p] = a[p >> 1]; a[p >> 1] = temp; p = p >> 1; } } /** * 打印数组中的数据 */ public void printHeap() { Arrays.stream(a).forEach(System.out::print); } public static void main(String[] args) { SimpleHeap heap = new SimpleHeap(10); heap.insert(6); heap.insert(8); heap.insert(3); heap.insert(9); heap.insert(4); heap.printHeap(); } }
删除堆顶元素
如果操作的是最大堆，删除堆顶元素以后，需要在剩余元素中找出第二大的元素，也就是左右子节点中找出最大的元素替换它们的父节点。直到最后的节点为叶子节点。此时最后堆化出来的堆不一定满足完全二叉树。
我们可以把最后一个节点放在堆顶，自上向下，对比父子节点的大小关系，互换两个节点。直到最后父子节点之间满足大小关系为止。这就是从上往下的堆化。
代码示例：
/** * 最大堆，移除堆顶元素 */ public void removeMax() { // 没有元素 if (count == 0) { return; } a[1] = a[count]; --count; heapify(a, count, 1); } private void heapify(int[] a, int n, int i) { while (true) { int maxSite = i; if ((i << 1) <= n && a[i] > a[i << 1]) { maxSite = i << 1; } if ((i << 1) + 1 <= n && a[i] > a[i << 1 + 1]) { maxSite = i << 1 + 1; } if (i == maxSite) { break; } swap(a, i, maxSite); i = maxSite; } }
时间复杂度
一个包含n个节点的完全二叉树，树的高度不会超过log2(n)，堆化的过程是顺着节点所在路径比较交换的，堆化的时间复杂度跟树的高度成正比，时间复杂度为O(logn)
基于堆的排序
一、原地建堆
使用原数组，不借助其他存储空间，原地建堆。
第一种方法是借助插入元素的思想，假设堆中只有一个数据，即下标为1的元素，把剩余的元素依次插入到堆中。
第二种方法是类似删除的思想，每次新插入的数据在堆顶，从上往下实现堆的方法。
第二种方法的起始点为倒数第二层开始，第一个不是叶子的节点开始。叶子节点没有子节点，不需要进行堆化。
假设共有 n 个节点，需要对 1 到 n/2 的节点进行堆化，下标 n/2+1 到 n 的节点是叶子节点，不需要堆化。需要注意边界问题和调整以后的子树是否还满足堆的性质
堆排序的建堆过程的时间复杂度为O(n)
每个节点堆化的时间复杂度为O(logn)，这里共有n/2+1个节点需要堆化，那么时间复杂度是不是O(nlogn)呢？然而并不是~
并不是所有节点的堆化时间复杂度都一样，节点的堆化和高度相关，我们只需要对每个节点的高度求和，得出的就是建堆的时间。
二、排序
建堆结束以后，数组中的数据已经按照大顶堆的特性排列。我们把堆顶的元素和最后一个元素交换位置。剩下的操作和删除堆顶元素的操作保持一致。
除去最后一个元素，我们把剩下的 n-1 个元素重新构成堆，然后重复前面的操作，当堆中只剩下一个元素的时候，排序工作就完成了。
复杂度
堆排序过程中，只需要个别临时存储空间，所以堆排序是原地稳定排序算法，堆排序主要包括建堆和排序两个操作，建堆过程中的时间复杂度为 O(n),排序的时间复杂度为O(nlogn)，所以堆排序的整体时间复杂度为O(nlogn)
稳定性
堆排序不是稳定的排序算法，排序的过程中，堆的最后一个节点跟堆顶节点互换的过程中，很有可能改变值相同数据的原始相对顺序。
代码示例：
import java.util.Arrays; /** * 堆排序 * @author: calos * @since: 2021/3/25 6:07 上午 **/ public class HeapSort { /** * 排序方法 * @param a 数组 */ public void sort(int[] a) { int len = a.length; initDown(a); for (int i = len - 1; i > 0; i--) { swap(a, 0, i); heapify(a, 0, i); } } /** * 类似插入新数据的方法，自下而上实现堆化 * @param a 数组 */ private void initUp(int[] a) { int len = a.length; for (int i = 1; i < len; i++) { int current = i; int parent = i >> 1; while (parent >= 0) { if (a[parent] >= a[current]) { break; } int temp = a[current]; a[current] = a[parent]; a[parent] = temp; current = parent; } } } /** * * 类似删除操作，自上而下实现删除操作 * @param a 数组 */ private void initDown(int[] a) { int len = a.length; for (int i = (len - 1) >> 1; i >= 0; i--) { heapify(a, i, len); } } /** * 删除堆顶元素时，需要的删除操作 * @param a 数字 * @param i 堆顶元素的位置 * @param n 数组的长度 */ private void heapify(int[] a, int i, int n) { int current = i; while (true) { int max = current; if ((current << 1) < n && a[current << 1] > a[max]) { max = current << 1; } if ((current << 1) + 1 < n && a[(current << 1) + 1] > a[max]) { max = (current << 1) + 1; } if (max == current) { break; } swap(a, current, max); current = max; } } /** * 交换数组的两个数字 * @param a 数组 * @param i 位置i * @param j 位置j */ private void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void main(String[] args) { int[] arr = {3, 5, 4, 1, 2, 6}; new HeapSort().sort(arr); Arrays.stream(arr).forEach(System.out::print); } }
为什么快速排序比堆排序性能好
- 堆排序数据访问的方式没有快速排序友好。堆化操作访问的数据都不是连续的，快排局部数据是顺序访问，堆排序这样对CPU缓存不友好。
- 同样的数据，排序过程中，堆排序算法的数据交换次数要多于快速排序。
快速排序的数据交换次数不会比逆序度多，堆排序的第一步是建堆，建堆的过程中会打乱数据原有的先后顺序，导致原数据的有序度减低，有序数据建堆后会变得无序。
