题解 | #寻找第K大#

利用数组 a 的前k个元素，建立 k 个元素的小根堆，然后遍历剩余的n-k的数，依次跟堆顶元素比较，如果比堆顶元素小，则放弃，如果比堆顶元素大，则加入堆并调整。遍历完成后，返回堆顶元素，即为第K大的数。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        // 利用数组 a 建立 k 个元素的小根堆，然后遍历剩余的n-k的数，依次跟堆顶元素比较
        // 如果比堆顶元素小，则放弃，如果比堆顶元素大，则加入堆并调整
        // 遍历完成后，返回堆顶元素
        initHeap(a, K);
        for(int i = K; i < n; i++) {
            addToHeap(a, i, K);
        }
        return a[0];
    }
    private void addToHeap(int[] a, int idx, int k){
        if(a[0] > a[idx]) {
            return;
        }
        a[0] = a[idx];
        adjust(a, 0, k);
    }
    
    private void initHeap(int[] a, int k) {
        int l = (k - 2) / 2;
        for (int i = k - 1; i >= l; i--) {
            int child = i;
            while(child != 0) {
                int parent = (child - 1) / 2;
                if(a[child] < a[parent]) {
                    swap(a, child, parent);
                    adjust(a, child, k);
                }
                child = parent;
            }
            
        }
    }
    
    private void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    
    private void adjust(int[] a, int start, int k) {
        while(true) {
            int minIdx = 2 * start + 1; 
            if (minIdx >= k) {
               break;
            }
            int right = 2 * start + 2; 
            if (right < k) {
                minIdx = a[minIdx] < a[right] ? minIdx:right;
            }
            if(a[start] > a[minIdx]) {
                swap(a, start, minIdx);
                start = minIdx;
            } else {
                break;
            }
        }
    }
}