解题思路：
乘着做这个题，顺便复习下堆排序。
先说堆排序是一个什么东西：
大顶堆升序，小顶堆降序。
随便定义的一个堆。
第一步：
此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。
注意：第一步已经把9弄上去了，所以只需要看9 5 6这三个数字是不是符合大顶堆，一看符合的，然后回到4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。
此时，我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。
注意：这里和root交换后的东西，后面已经不放在堆里面进行排了。
1 import java.util.ArrayList; 2 public class Solution { 3 public ArrayList GetLeastNumbers_Solution(int [] input, int k) { 4 5 ArrayList res = new ArrayList<>(); 6 7 if(k>input.length || input==null) 8 return res; 9 // 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整10 // 也就是说，是按照自下而上，每一层都是自右向左来进行调整的11 // 注意，这里元素的索引是从0开始的12 // 另一件需要注意的事情，这里的建堆，是用堆调整的方式来做的13 // 堆调整的逻辑在建堆和后续排序过程中复用的14 for(int i=k/2-1;i>=0;i--)15 {16 Adjust(input,i,k-1);//从最后一个非叶子节点开始17 }18 19 for(int j=k;j input[i])52 {53 break;54 }55 else56 {57 swap(input, i, k);58 // 下面就是非常关键的一步了59 // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？60 // 所以，循环对子节点所在的树继续进行判断61 k = i;62 }63 }64 }65 66 public void swap(int []input,int a,int b)67 {68 int temp = input[a];69 input[a]=input[b];70 input[b] = temp;71 }72 73 74 }
1 class Solution { 2 public int findKthLargest(int[] input, int k) { 3 4 if(input.length==1) 5 return input[0]; 6 int length = input.length; 7 for(int i=k/2-1;i>=0;i--) 8 { 9 Adjust(input,i,length-1);10 }11 12 for(int j = length - 1; j >=k; j--)13 {14 if(input[j]>input[0])15 {16 int temp = input[0];17 input[0] = input[j];18 input[j] = temp;19 Adjust(input,0,k-1);20 }21 }22 23 return input[0];24 25 26 }27 28 public void Adjust(int []input,int k,int length)29 {30 int temp = input[k];31 for(int i=2*k+1;i<=length;i=2*i+1)32 {33 if(i input[i+1])34 {35 i++;36 }37 if(temp