算法学习 leetcode 703 实时判断数据中的第K大元素

题目：实时判断数据流中的第K大元素

解这道题，适合的数据结构就是小顶堆了。

小顶堆是一个二叉树数据结构，在小顶堆中，根节点最小，其子节点都比自己的父节点大，维护一个大小为K个元素的小顶堆，堆中所有元素就是前k大的元素了。

具体是解法，可以用Java 的 PriorityQueue，名为优先级队列，但是这个队列不是按照先进先出的，而是按照优先级来出队列，并且PriorityQueue默认就是通过二叉小顶堆实现。

因为堆顶元素值是整个堆中最小的，所以每次要放入的数，先和堆顶元素比较，如果小于等于堆顶元素，那么不需要放入堆中，如果大于堆顶元素，那么堆顶元素出队，将这个元素存入PriorityQueue中。

package com.itzhimei.study.algorithm;

import java.util.PriorityQueue;

public class GetKth {
    private int k;
    final PriorityQueue<Integer> q;
    public GetKth(int k) {
        this.k = k;
        q = new PriorityQueue<>(k);
    }

    public void addElem(int n) {
       if(q.size() < k) {
           //没满就直接入队
           q.offer(n);
       } else if(q.peek() < n) {
           //满了则进行比较,如果n大于堆顶元素,则进入优先级队列
           q.poll();
           q.offer(n);
       }
    }

    public static void main(String[] args) {
        GetKth g = new GetKth(5);
        int[] nums = {5,3,7,8,2,15,23,55};
        for(int n:nums) {
            g.addElem(n);
        }
        System.out.println("第5大的数字是：" + g.q.peek());
    }
}

知识点：

小顶堆/大顶堆，能求前k大/小的一组数。

堆的应用：优先级队列–PriorityQueue，能求第K大的数。