2021-06-26堆

概念

1. 一个完全二叉树。
2. 每个节点的值都必须大于等于[大顶堆]（或小于等于[小顶堆]）其子树中每个节点的值。
3. 说明：堆其实就是一种完全二叉树，最常用的存储方式就是数组。[说明：堆中序遍历就是有序的数组]

存储

数组

操作

插入一个元素和删除堆顶元素

堆排序

1. 借助堆实现的排序算法。
2. 时间复杂度非常稳定，是O(n*logn)。
3. 是原地排序算法。

如何基于堆去实现排序？

第一步 建堆

• 思路1：从前往后处理数组数据，并且每个数据插入堆中时，都从下往上堆化。

• 思路2：从后往前处理数组，并且每个数据都是从上往下堆化。

  //小顶堆
  PriorityQueue<Integer> small = new PriorityQueue<>();
  //大顶堆
  PriorityQueue<Integer> big = new PriorityQueue<>((x, y) -> (y - x));
  

第二步 排序：

1. 堆顶跟最后一个元素交换，把下标为n的元素放到堆顶，通过堆化的方法，将剩下的n-1个元素重新构建成堆。
2. 堆化完成之后，取堆顶元素，放到下标是n-1的位置。
3. 一直重复这个过程，直到最后堆中只剩下标为1的一个元素，排序工作就完成了。

为什么快排比堆排序性能好？

1. 堆排序数据访问的方式没有快排友好。
2. 同样的数据，在排序过程中，堆排序算法的数据交换次数多于快速排序。

应用

1. 优先级队列
2. 针对静态/动态数据集合求Top K。
3. 求动态数据集合中的中位数。