堆排序基于完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
将一维数组看做一颗完全二叉树 如数组[9,15,7,3,25,13,8,21],可以观察出以下规律
arr[i]为arr[2*i+1],arr[2*i+2]的父节点
堆的定义
最大堆父节点大于等于子节点,体现在数组中就是 arr[i] >= arr[2*i+1]&&arr[i] >= arr[2*i+2]
最小堆 父节点小于等于子节点,体现在数组中就是arr[i <= arr[2*i+1]&&arr[i] <= arr[2*i+2]
上例对应的最大堆为
堆排序是如何实现的?
假设为正序排列,将数组看做完全二叉树
- 构建为最大堆,此时首节点arr[0]就是最大的值
- 依次将首节点与无序最大堆的中最后一个节点交换,然后调整堆使其满足最大堆要求
这样就构建了一个从尾节点到首节点依次减小的堆,正好满足数组的正序排列要求
如何构建最大堆?
- 从最后一个非叶节点(arr[n/2-1]])开始,提升其子节点(可能为非叶节点)中的最大值到当前节点,并将当前节点值下放的可能的最底层.
- 对前面的非叶节点重复 1
这样就构造出了最大堆
在首节点交换后,如何调整堆?
当首节点交换后,最后一个节点已经有序,可以忽略了.此时堆中只有首节点是不符合最大堆的定义的.对首节点应用构建最大堆的步骤即可,注意要忽略掉已经有序的尾节点
算法实现
/**
* 将一维数组看做一颗二叉树 父节点和子节点的关系为 Nk~=N2k+1,N2k+2
* 1. 构建堆
* 2. 调整堆
*/
public class SimpleHeapSort {
public static void main(String[] args) {
int[] arr = new int[]{6545,1,4456, 5, 4, 65, 63,5445};
heapSort(arr);
for (int n : arr) {
System.out.println(n);
}
}
private static void heapSort(int[] arr) {
//从最后一个节点开始扫描,构建最大堆
for (int i = arr.length / 2 - 1; i >= 0; i--) {
adjustHeap(arr, i, arr.length);
}
//依次将堆顶最大值移到当前的末尾,构建有序数组
for (int j = arr.length - 1; j > 0; j--) {
swap(arr, 0, j);
adjustHeap(arr, 0, j);
}
}
private static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i];
int k = 2 * i + 1;
int j = i;
while (k < length) {
if (k+1<length&&arr[k] < arr[k + 1]) {
k = k + 1;
}
if (temp < arr[k]) {
arr[j] = arr[k];
j = k;
}else{
break;
}
k = k * 2 + 1;
}
arr[j] = temp;
}
private static void swap(int[] arrays, int i, int j) {
int temp = arrays[i];
arrays[i] = arrays[j];
arrays[j] = temp;
}
}
重建堆的时间复杂度为O(NlogN)
树的高度为k=lgN+1,从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k次,排序过程中的筛选次数不超过下式:
2(lg(N-1)+lg(N-2)+lg(N-3)+lg(2))<2n()lgN
建堆的时间复杂度为O(N):
链接：
https://www.nowcoder.com/questionTerminal/385157a6b64540c3b233bd12f8a83ee7
来源：牛客网如果从底部最后的父节点开始建堆，那么我们可以大概算一下： 假如有N个节点，那么高度为H=logN，最后一层每个父节点最多只需要下调1次，倒数第二层最多只需要下调2次，顶点最多需要下调H次，而最后一层父节点共有2(H-1)个,倒数第二层公有2(H-2),顶点只有1(2^0)个，所以总共的时间复杂度为s = 1 * 2^(H-1) + 2 * 2^(H-2) + ... + (H-1) * 2^1 + H * 2^0 将H代入后s= 2N - 2 - log2(N)，近似的时间复杂度就是O(N)。
