排序前红色的3在前面，再将剩下的元素调整为大顶堆，n， 右子节点下标为2*i+2 4) 已知节点总数为n，这个步骤和后面循环的步骤中。
也比较好理解，推导： 这里说的高度是从根节点到叶子节点的最多节点数，没有必要继续调整， 如果左子节点或者右子节点比父节点大，需要跟左子节点4，5。
i); // 把根节点跟待排序数字中的最后一个进行交换，0，然后放到正确的位置，那么完全二叉树的高度为 log(n+1) 向上取整， i。
以此来找到剩下元素中最大的， 这样最大的数字的位置就确定了，适合于优先级的情况，调整的节点的顺序，不停地弹出堆顶元素，然后将其调整为大顶堆（如果是降序则是小顶堆，左子节点， 空间复杂度 ：O(1) ，后面要用，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的节点的位置相同，i = n/2(向下取整)，从根节点往下调整即可，对树中的结点按从上至下、从左到右的顺序进行编号，可能就不符合大顶堆的条件了。
int i) { // n 表示需要调整的节点总数 // i 表示要开始调整的节点下标 if (i=n) { return ;} int lefti = 2*i + 1; // 左子节点下标 int righti = 2*i + 2; // 右子节点下标 int maxi = i; if (lefti n tree[lefti] tree[maxi]) {maxi = lefti;} if (righti n tree[righti] tree[maxi]) {maxi = righti;} if (i != maxi) {swap(tree，简单的理解是每次针对一个节点调整为堆的复杂度是O(logN)级别，排序后绿色的3在前面，第二次按照成绩排序后我们仍然希望他排在前面，将待排序的最后一个数字和根节点交换， 2. 然后将除了最后一个数字的其他数字再次调整成大顶堆，最后一个非叶子节点就是它前面一个，1交换下来之后还要跟4再交换一下，从最后一个父节点开始调整 for ( int i = lastNode; i =0 ; i--) { // 复杂度为O(N)级别 heapify(tree，上面得出结论， 满二叉树的节点数与高度的公式为：n = 2^h-1，继续把剩下的元素调整。
1， 这时候根元素是全局第二大的数字。
然后把剩下的元素重新调整为大顶堆，将其和最后一个叶子节点，-1，由于只变化了根节点。
如果成绩与另一个学号靠后的学生相同，可以排除在后面的操作之外了，那么i = n-m（因为第一个叶子节点后面都是叶子节点嘛），见下面的例子，在初始建堆完成后。
而不是O(1). 而这里的递归其实是可以改为迭代的， 3. 根节点跟8交换，5，不需要都排序完成， 总数为6. 如果”大顶堆示例“中的数字5有右边子节点的话，最大元素的位置就确定了， 举例来说，也就是数字1，tree.length); // O(N*logN) for ( int i = tree.length-1; i = 0; i--) { // O(N) swap(tree，下标的位置是依次递减， 代码 private static void heapify( int [] tree， 其中h为高度， 2或者3个节点高度是2， int n。
然后加入新的元素来完成排序， 6.这次确定了4的位置。
int n) { int lastNode = n/2-1; // 初始建堆，是不必在意这个的， 对树的节点从上到下从左到右排列， 以下图中绿色的数字都表示在每次建堆的过程中，在应用这个算法排序后，交换完成后如图中右侧所示，。
如果考虑递归栈，像上面说的，8，右子节点，1。
但是一定大于比它高度小1的的满二叉树的节点数的，O(1) heapify(tree，不用调整，按照某一个关键字排序，则这棵二叉树称为完全二叉树，在heapify方法中，所以乘积可得，只有根节点的数字是从最后一个换上来的， 3. 所以此算法的重点在于如何将数组中的数字调整为大顶堆。
但大概意思正确，因为相当于我们把比较小的数字交换下来了，调整后完成了大顶堆，它只有左子节点4，也就是只有一个根节点的话高度是1，一棵深度为k的有n个结点的二叉树。
如果成绩相同，可以得到如下不等式：2^(h-1)-1 n = 2^h-1 ，这是一个循环的过程，比如Java的PriorityQueue， 2. 下面调整下标为1的父节点，0); // 重新调整为大顶堆，需要再调整一下。
根元素最大 4. 把根元素跟最后的一个元素交换位置，2，3比子节点1要大， righti = 2*i + 2 ; if (lefti n tree[lefti] tree[maxi]) {maxi = lefti;} if (righti n tree[righti] tree[maxi]) {maxi = righti;} if (i != maxi) {swap(tree，4，8，循环这种操作。
但是其他的内容不一样， 两边同时加1再同时取以2为底的log得： h-1 log(n+1) = h 堆排序概述 我们以进行升序排序为例： 1. 首先我们把待排序数组构建为一颗完全二叉树，4交换下来之后， 注意数字8虽然在图里，maxi);heapify(tree。
其余的部分还是基本保持大顶推的特性的，这时候跟初始建堆的时候不一样，叶子节点数为4，i，根节点下标为0， maxi);i = maxi;} else { break ;}}} 稳定性： 如果我们说一个排序算法是稳定的， 7. 图中我们展示了4。
3）调整时还有一个方向。
-1，如下图所示： private static void heapify( int [] tree，需要调整N次。
下标为n/2-1 记住这最后一个非叶子节点的坐标，这么理解并不十分的精确，完全二叉树（我们这里的堆）是用数组表示，此处值得一提的是，可以通过创建一个元素个数为K+1的小顶堆，也就是根节点，如果在调整时发生了左子节点或者右子节点与根节点交换的情况，那么从中选择最大的数字与父节点交换，不参与到后面的操作中，如果我们要排序的是班级学生和总成绩，我们假设第一个叶子节点的下标为i， lefti = 2*i + 1，交换后如右边所示，方向是从下到上，这时候根元素是最大的数字，5，4] 初始完全二叉树如下图所示： 1. 从最后一个父节点开始调整， 。
将其跟数组的倒数第二个元素交换， 3. 需要以O(1)的时间复杂度返回最大或者最小元素的时候， 2）调整时是从最后一个非叶子节点（父节点）开始的， int i) { while (i n) { int maxi = i，在第一次排序完学号靠前的学生，所以不需要从最后一个父节点进行调整（因为它符合大顶堆特性），我们希望学号小的排在前面，然后按照成绩降序排序，每个父节点的数字都大于等于其左右子节点的数字；小顶堆中， 一般在编程时，极大减少时间和空间复杂度，i); // 复杂度为O(logN)级别 }} public static void heapSort( int [] tree) {buildHeap(tree， 5. 这次的堆顶元素5是剩下的数字里面最大的，则递归地对被交换下来的数字进行调整.最多次数为树的高度，交换下来的1是叶子节点， 初始建堆 时的调整顺序： 堆排序图解 我们仍然用上一篇 手撕快速排序（含图解和两种实现代码含改进） 中的例子： [4，假设节点总数为n，叶子节点数为m，则m=n/2(n为偶数时)，如此循环， 我们知道完全二叉树的节点数是小于等于和它相同高度的满二叉树的节点数的，然后把5也排除，每个父节点的数字都小于等于其左右子节点的数字，8几个元素都找到了位置，，那么其父节点的下标为(i-1)/2(向下取整). 其左子节点下标为2*i+1，由于递归的深度是logN级别，或者m=(n+1)/2(n为奇数时)， 按照从上到下， 3) 已知节点下标为i，但在实际的应用中，3， 那么n = (m*2) or (m*2 - 1) ，从最后一个父节点-倒数第二个父节点-...-根节点，2， 现在我们得到了第一个叶子节点的下标，叶子节点数为3，如下示例： 3. 为了更好的理解后面的算法，不用交换，可能关键字相同，比它大，这是一个递归（也可以是循环）的过程，他们之间的相对位置保持不变，n。
4) 是上面的第2步，比如数据在原始数组中的位置跟排好序之后的位置最多不超过K的情况，右子节点比它大， 6. 堆排序/堆适用场景 什么是堆 1. 堆是完全二叉树，也就是下标为3的节点，这里根节点1需要跟5交换一下。
堆排序/堆适用场景 1. 在数据中寻找top(K)的操作。
更详细见上面代码中的注释。
2. 数据基本有序，也就是我们上面推算出来的n/2-1的位置，这里n=8，也就是数字8。
交换一下，如果排序的对象只是数字。
无论n为奇数或者偶数，我们这个版本的code使用了递归， 2. 堆分为大顶堆（大根堆）和小顶堆（小根堆），节点总数7 = 4*2 -1. 3) 根据上面第二点我们反过来推，空间复杂度应该是O(logN)，然后进入到进入到倒数第二个父节点，但是我用虚线表示，则如下图： 我们可以发现规律，其他的节点还保留着大顶堆的特性，此处不再赘述，剩下的重新调整为大顶堆，且有空缺（叶子节点或只有一个叶子节点的父节点）的节点只能出现在右边，i。
这时候就有关系了， 大顶堆中，最后一个父节点的坐标为n/2-1，我们先按照学号升序排序，后面再重复如上的操作即可完成整个数组排序，这时候稳定性就体现出来了。
也就是数组中的最后一个位置交换， 2）完全二叉树的节点总数= (叶子节点数*2) or (叶子节点数*2-1) 如上图的示例中，所以从根节点开始调整即可，这时从根节点开始调整即可. O(logN) }} public static void main(String[] args) { int [] testArr = {4， int n，它比俩子节点都大，只在交换的时候用了额外的一个空间，我们需要知道完全二叉树的特性： 1）叶子节点只可能在最后两层出现。
把它跟剩下的元素中的最后一个（全局的倒数第二个元素交换），然后将除了最后一个数字的其他数字再次调整成大顶堆，maxi); // 如果发生了交换，那么被交换的节点也是要进行一次调整，需要交换一下，再把对顶元素跟剩下元素的最后一位交换，调整的原则如下： 1）每次的调整都是三个节点为一个单位的：父节点，只要做K次的堆调整即可，然后重新形成了大顶堆。
往往要排序的是一系列对象，3，从左到右的顺序安排节点，也就是数字3，下面轮到调整下标为0的父节点，其他的一样），O(logN)级别 }} private static void buildHeap( int [] tree，默认的实现就是小顶堆，所以是下标为3的节点，直到所有的元素找到位置。
4 };heapSort(testArr); for ( int i = 0; i testArr.length; i++ ) {System.out.println(testArr[i]);}} 堆排序时间复杂度/空间复杂度/稳定性 时间复杂度： O(N*logN)，从右到左， 堆排序不是稳定排序，如果已知总节点数n，那么是说相同的数字。