215. 數組中的第K個最大元素

給定整數數組?nums?和整數?k，請返回數組中第?k?個最大的元素。

請注意，你需要找的是數組排序后的第?k?個最大的元素，而不是第?k?個不同的元素。

你必須設計并實現時間復雜度為?O(n)?的算法解決此問題。

class Solution {
public:void maxHeapify(vector<int>& a, int i, int heapSize) {int l = i * 2 + 1, r = i * 2 + 2, largest = i;if (l < heapSize && a[l] > a[largest]) {largest = l;} if (r < heapSize && a[r] > a[largest]) {largest = r;}if (largest != i) {swap(a[i], a[largest]);maxHeapify(a, largest, heapSize);}}void buildMaxHeap(vector<int>& a, int heapSize) {for (int i = heapSize / 2 - 1; i >= 0; --i) {maxHeapify(a, i, heapSize);} }int findKthLargest(vector<int>& nums, int k) {int heapSize = nums.size();buildMaxHeap(nums, heapSize);for (int i = nums.size() - 1; i >= nums.size() - k + 1; --i) {swap(nums[0], nums[i]);--heapSize;maxHeapify(nums, 0, heapSize);}return nums[0];}
};

堆排序方法，實際上時間復雜度不滿足要求，但主要想學一學堆排序

堆是一個完全二叉樹，對于最大堆，根節點一定大于其子節點

這里的邏輯就是，將整個數組構建成最大堆，執行k-1次"移除堆頂元素"操作（將堆頂元素與堆尾交換并調整堆），此時堆頂元素就是第k大的元素

主要內容還是如何維護最大堆，這里通過將棧頂與棧末交換實現棧頂元素移除，接著不斷交換根節點和較大的子節點，直至根節點大于兩個子節點，從而保持最大棧的性質