公众号merlinsea
- 堆的介绍
- 堆是一种数据结构，其底层实现是一个完全二叉树，这个完全二叉树满足：任何一个非叶子节点的值都不大于（或者不小于）其左右孩子节点的值。若保证父节点的值大于等于孩子节点的值则称之为大根堆，若保证父节点的值小于等于其孩子节点的值则称之为小根堆。
- 堆排序的介绍
- 根据堆堆定义可以知道，堆这棵完全二叉树的根节点是整棵树中的最大值（或者最小值），因此可以将根节点和最后一个节点交换位置，这样我们可以知道有序序列就增多一位，无序序列就减少一位，然后将无序序列重新调整为一个堆，不断重复这个过程，我们就得到了堆排序。
- 堆排序的本质依旧是选择类排序，但和简单选择排序相比，我们每次选择最值的时间复杂度是O(logn)
- 堆排序（从小到大排序为例）的流程如下：
- 将输入的初始序列建立为一个大根堆
- 将堆顶元素和最后一个元素交换位置
- 将无序序列重新调整为一个堆
- 重复第2步骤和第3步骤，直到整个序列有序。
public class Main { public static void main(String[] args) { int[] array = new int[]{7,29,32,58,11,45,35,23,45,49}; System.out.println("元素序列"); for(int k : array){ System.out.printf("%d \t",k); } System.out.println(); creadMaxHeap(array); System.out.println("初始化为大根堆"); for(int k : array){ System.out.printf("%d \t",k); } System.out.println(); heapSort(array); System.out.println("堆排序后"); for(int k : array){ System.out.printf("%d \t",k); } System.out.println(); } //堆排序 public static void heapSort(int[] arr){ //无序序列的最后的位置 int lastIdx = arr.length - 1; while(lastIdx>0){ // 交换 int temp = arr[0]; arr[0] = arr[lastIdx]; arr[lastIdx] = temp; lastIdx--; //调整堆 int lastPar = (lastIdx+1)/2-1; int cur = 0; while(cur<=lastPar){ //说明cur 有孩子节点 int maxChild = cur*2+1; // 没次调整一个，无序序列就少一个，那么lastIdx就减少1 if(maxChild+1<=lastIdx && arr[maxChild]<arr[maxChild+1]){ maxChild = maxChild + 1; } if(arr[maxChild]>arr[cur]) { //向下调整 temp = arr[cur]; arr[cur] = arr[maxChild]; arr[maxChild] = temp; cur = maxChild; }else{ break; } } } } //建立大根堆 public static void creadMaxHeap(int[] arr){ int lastPar = arr.length /2 - 1; int cur = lastPar; while(cur>=0){ int par = cur; while(par<=lastPar) { // 假设孩子节点中最大值是左孩子 int maxChild = par * 2 + 1; if (maxChild + 1 < arr.length && arr[maxChild + 1] > arr[maxChild]) { //若有右孩子并且右孩子是孩子节点中更大的那个，移动maxChild maxChild = maxChild + 1; } if (arr[maxChild] > arr[par]) { //需要交换位置 int temp = arr[maxChild]; arr[maxChild] = arr[par]; arr[par] = temp; //继续向下调整 par = maxChild; } else { break; } } cur--; } } }
- 堆排序的性能分析
- 算法时间复杂度：堆排序的时间主要耗费在将无序序列部分调整为堆的过程，每次调整需要比较的最大次数是完全二叉树的高度，因此堆排序的时间复杂度的上限是O(nlogn)
- 算法空间复杂度：由于堆排序是基于原始输入的数组进行排序的，因此空间复杂度是O(1)
- 算法稳定性分析：堆排序是不稳定排序。
算法训练营永久刷题班元旦优惠价，超低价格永久刷题。加入我们可以一起备战明年的春招笔试，快来参加吧～
算法训练营元旦福利
奔跑的小梁，公众号：梁霖编程工具库leetcode刷题直播教学，手把手带你刷题，元旦价格优惠通知，超低价格永久刷题
