题解 | #寻找第K大#

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        return headSort(a, n, K);
    }    
    int headSort(int[] a, int n, int K){
        int i;
        int end = n - 1;
        int count = 0 ;
        for(i=(end-1)/2 ; i>=0 ; i--)//从第一个非叶子节点开始调整
            headAdjest(a, i, end);
        count++;
        for(i=end ; i>0 ; i--, count++){
           int temp = a[0];
            a[0] = a[i];
            a[i] = temp;
            if(K == count)//找到第K个大的数
                return a[i];
            headAdjest(a,0,i-1);
        }
        return a[n-K];
    }
    void headAdjest(int[] a, int start, int end){
        int temp = a[start];
        int j;
        
        for(j=start*2+1 ; j<=end ; j=j*2+1){
            if(j<end && a[j]<a[j+1])j++;//寻找孩子中更大的一个
            if(temp > a[j])break;//父》子 无需调整
            a[start] = a[j];
            start = j;
        }
        a[start] = temp;
    }
}