作者：mobiledu2502861377 | 来源：互联网 | 2023-10-16 12:55
1.完全二叉树的概念
除了最后一层之外的其它每一层都被完全填充，并且所有的节点都保证向左对齐。
2.堆的结构
首先，堆结构就是一棵完全二叉树；
堆分为大根堆（任何一棵子树的最大值都在头部）；小根堆（任何一棵子树的最小值都在头部）；
3.堆排序的思路
3.1 将数组变为堆的结构（大根堆）
3.2 将堆顶数据和最后一个数据交换，输出新的最后一个数据（也就是最大值），调整剩余的数据变成大根堆
4.代码实现
4.1 将数组变为堆结构
思路：假设要操作的数据（就是把数据插入到堆里面）下标是i，将它和它的父节点（(i-1)/2）比较,如果比他的父节点大，就交换；再接着一直往上比较，一直到它比父节点小了。
1.构造堆结构(从下往上走)public static void heapInsert(int[] arr, int i) {while(arr[i]>arr[(i-1)/2]) {swap(arr, i, (i-1)/2);i=(i-1)/2;} }
4.2 在3.2中交换以后，重新调整堆结构
思路：确定要调整结构的数据坐标，比较他的左右孩子，把其中较大的和它比较，孩子大就交换，在新位置重新调整堆结构；否则的话，不用调整，直接跳出。
//2.重新调整堆结构（堆顶数据变换之后，要重新调整堆结构）public static void heapify(int[] arr,int index,int heapSize) {int left=2*index+1;while(left 4.3 总流程
//1.数组中根据每一个元素构造堆结构
for(int i=0;i}//2.堆顶元素和最后一个元素互换，堆的尺寸-1，重新调整堆结构,最大的堆顶元素就找到了。
int heapSize=a.length;
swap(a,0,--heapSize);
while(heapSize>0){heapify(a,o,heapSize);swap(a,0,--heapSize);
}
5.时间复杂度分析
堆排序的时间复杂度是O(nlogn)，额外的空间复杂度是O(1);
京公网安备 11010802041100号