正文之前
这一篇文章介绍一下堆的概念，以及堆排序
- 基本概念、最大/最小堆
- 堆排序
- 分析
正文
1. 什么是堆
堆不是单独的一种结构，而是一种树状数据结构，通过二叉堆来实现，二叉堆也就是二叉树的一种，讲白了就是类似二叉树，只不过满足：
-
除了最底层，其他层全满，最底层按照从左至右的顺序填入节点（完全二叉树）
-
父节点大于等于或小于等于子节点，这两种情况就成为了最大堆/最小堆的定义：
最大堆：任意节点大于等于它的所有后裔（不仅是子节点，还有子节点的子节点等等），最大节点在堆顶
最小堆：任意节点小于等于它的所有后裔，最小节点在堆顶
还有一种叫法是大顶堆/小顶堆
给个图吧：
2. 堆排序
堆排序的步骤是这样的：
- 用给定数组构建堆
- 一个循环，每次选择堆顶元素，调换至末尾，然后缩小范围（相当于取出队首元素，添加至末尾，一轮循环后，数组就有序了）
首先我们先来写一下确定节点位置的代码：
/**
* 因为下标是从 0 开始的，在获取节点
* 的时候要多 + 1
* @param node 给定节点的位置
* @return 对应节点位置
*/
public int leftNode(int node){
return 2 * node + 1;
}
public int rightNode(int node){
return 2 * node + 2;
}
public int parentNode(int node){
return (node - 1) / 2;
}
这里的 parentNode() 方法没有用到，但是这个计算父节点的方式下面要用到，然后我们来写调整堆的方法，采用递归的方法，每一次递归我们只针对某个节点以及它的子节点：
public void maxHeapify(int[] heap, int length, int node){
//获取左右节点
int left = leftNode(node);
int right = rightNode(node);
//当前最大节点（堆顶）
int largest = node;
//如果左子节点的值大于父节点的值，就改变 largest 的指向
if (left < length && heap[left] > heap[largest]){
largest = left;
}
//如果右子节点的值大于父节点的值，就改变 largest 的指向
if (right < length && heap[right] > heap[largest]){
largest = right;
}
//如果 largest 的指向改变了，就说明要调整堆，调换两个元素的位置
if (largest != node){
int temp = heap[node];
heap[node] = heap[largest];
heap[largest] = temp;
} else {
return;
}
maxHeapify(heap, length, largest);
}
然后是构建堆的方法，就像在上面的代码中定义的寻找父节点位置的方法一样，(heap.length - 1) 代表的是堆中最后一个节点位置，(heap.length - 1) / 2 是最后一个节点的父节点的位置，从这里开始构建堆，避免多次不必要的递归，提高效率：
public void buildHeap(int[] heap){
for (int i = (heap.length - 1) / 2; i >= 0 ; i--) {
maxHeapify(heap, heap.length, i);
}
}
最后便是堆排序的代码：
public void heapSort(int[] heap){
for (int i = heap.length - 1; i > 0; i--) {
int temp = heap[0];
heap[0] = heap[i];
heap[i] = temp;
maxHeapify(heap, i, 0);
}
}
划重点：这里之所以要用 i 来代替 heap.length，是因为我们要模拟从堆顶删除节点，实际上并没有删除，只是把它换到了末尾，所以通过堆大小 - 1 来达到模拟删除的效果
画了个堆排序的过程图：
数组 [3,5,2,6,4,1,10,7,9,8] 构建完后就是图中 1 的堆，然后把 4 和 10 对调，再调整堆，得到图中 2 的堆，把 6 和 9 对调，然后调整堆，以此类推：
接下来是计算的结果：
构建最大堆进行排序的结果是升序，因为大的节点在末尾，如果要降序排列，就构建最小堆
3. 分析
- 时间复杂度：
时间都花在了一开始的构建堆和接下来的调整堆过程，对于 n 个数：
首先是新建堆，时间复杂度 O(n)
每一次的调整堆都是 logn，总共有 n - 1 次，为 (n - 1) * logn = nlogn - logn
所以堆排序的时间复杂度是 O(nlogn)
- 空间复杂度
O(1)，因为是原地排序，没有借助其它辅助结构
- 稳定性
不稳定
网友评论