题目：

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

思路：

        可以用快速选择，但是我这里主要介绍priority_queue这个容器。

priority_queue:

        这个容器就是优先队列，默认存储的是最大堆，也就是：   

    10
   /  \
  3    5 这种根节点大于下面每一个节点的就叫最大堆。相反就是最小堆，那么我们应该怎么去传递参数呢？priority_queue<int,  vector<int>,  greater<int>> 这个就是最小堆的定义了。

//         priority_queue<
//     typename T,                   // 数据类型
//     typename Container = vector<T>, // 底层容器（默认 vector）
//     typename Compare = less<T>      // 比较方式（默认是最大堆）
// >
//这个greater 返回是不是a > b?是的话就是返回true,默认情况下的优先队列是最小堆

对于队列我们知道c++内置函数有top();push();front(),back();pop()等，我们这里要返回的是第k个最大的元素。但是我们的优先队列是没有内置函数front的也就是不能访问第一个元素。所以选着最小端。

所以在c++中实现这个功能就很简单：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> pq;
        for(int &num : nums){
            pq.push(num);
            if(pq.size() > k) pq.pop();
        }
        return pq.top();
    }
};

想了解这个priority_queue（最小端怎么实现的可以看下面的代码）

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

class Minheap{
private:
    vector<int> heap;

    //向上调整，插入元素后维持性质
    void heapifyUp(int idx){
        while(idx > 0){
            int parent = (idx - 1) / 2;
            if(heap[parent] <= heap[idx]) break;
            swap(heap[parent], heap[idx]);
            idx = parent;
        }
    }

    //向下调整，删除堆项后维持性质

    void heapifyDown(int idx){
        int n = heap.size();
        while(true){
            int left = (idx * 2) + 1;
            int right = (idx * 2) + 2;
            int smallest = idx;
            if (left < n && heap[left] < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right; 
            //如果改删除的节点就是最小的（因为上面已经跟左右孩子比较了）
            if (smallest == idx) break;
            swap(heap[idx], heap[smallest]);
            idx = smallest;
        }    
    }
public:
    void push(int val){
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }

    void pop(){
        if(heap.empty()) throw runtime_error("nullptr");
        heap[0] = heap.back();
        heap.pop_back();
        if(!heap.empty()) heapifyDown(0);
    }

    int top(){
        if(heap.empty()) throw runtime_error("nullptr");
        return heap[0];
    }

    bool empty() const {return heap.empty();}//这个const的意思是
//“我保证在这个 size() 函数内部，不会修改类的任何成员变量。”

// 也就是说：

// 不允许对成员变量 heap 执行赋值、push_back、pop_back 等修改操作；

// 不允许调用非 const 成员函数；

// 只能读取成员变量。
    bool size() const {return heap.size();}


};

希望看完了能更好加深你对优先队列的理解