堆
什么是堆?
① 对是一个完全二叉树 ; ② 堆中的每个节点的值都必须 >=(或者<=)其子树中每个节点。
如何实现一个堆
- 如何存储一个堆:完全二叉树,用数组最好了。
插入完全二叉树中,也就是插入到数组的最后一个位置。
此时破坏了堆的特性,需要调整(也叫堆化):① 从下往上 比较交换直到符合规则
② 从上往下比较交换直到符合规则
- 删除
堆的插入删除操作都是顺着节点路径比较交换,完全二叉树的高度log2n,因此时间复杂度O(logn)
堆排序
借助堆结构的特点,把数组中数据位置对应到堆上对应位置,通过调整堆来对数组中数据进行排序。
对一组数据进行堆排序(以大顶堆为例)。
- 一组数据可以对应成一个完全二叉树。
- 对完全二叉树进行调整(也就是堆化)成堆。这一步类似插入操作,插入后的数据最终是在叶子节点上的。因此从最后一个节点开始从上往下进行堆化。节点n是叶子节点没有子节点因此从他的父节点开始。
private static void buildHeap(int[] a, int n) { for (int i = n/2; i >= 1; --i) {// 它是完全二叉树,因此有子节点的父节点i向上肯定都是父节点 heapify(a, n, i); }}private static void heapify(int[] a, int n, int i) { while (true) { // 交换后节点下边的子树又需要重新刷新位置 int maxPos = i; if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2; if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1; if (maxPos == i) break; swap(a, i, maxPos); i = maxPos; }}复制代码
- 排序 大顶堆已经排序好了,现在堆顶的元素肯定是数组中最大值,因为要原地排序且不能破坏堆的结构因此将堆顶元素与尾节点交换(类似删除操作),之后对新顶节点进行自上向下堆化(堆的范围1~n-1),完成后,堆顶又是最大元素。以此类推,每次将堆顶拿出,也就是每次找到剩余元素的最大值。重复n次所有元素就都排好了。
// n 表示数据的个数,数组 a 中的数据从下标 1 到 n 的位置。public static void sort(int[] a, int n) { buildHeap(a, n); int k = n; while (k > 1) { swap(a, 1, k); --k; heapify(a, k, 1); }}复制代码
堆排序的测评
空间复杂度O(n)
时间复杂度O(nlogn)
不稳定排序
为什么实际开发中快速排序好于堆排序?
- 堆排序数据访问方式没有快速排序友好:快:顺序(CPU缓存友好);堆:跳着
- 对于同样数据,在排序过程中,堆排序算法的数据交换次数多于快排。
应用
堆的排序过程中,每次都会找出剩余元素中最大的元素,因此可以应用于求topN