C++ solutions by applying heap

• Generally applying the property of heap - anytime the top value of the heap should be the maximum. Solution #1 is to write my own heap:

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
vector <int> heap;
for (int i(0);i<nums.size();i++) {
}
for (int i(0);i<k-1;i++) {
removeNodes(heap);
}
return heap[0];
}
void addNodes(vector<int> &heap, int val) {
heap.push_back(val);
int ichild(heap.size()-1);
int iparent((ichild-1)/2);
while (heap.size()>1 && heap[ichild]>heap[iparent]) {
swap(heap[iparent],heap[ichild]);
ichild=iparent;
iparent=(ichild-1)/2;
}
}
void removeNodes(vector<int> &heap) {
if (!heap.size()) return;
heap[0]=heap[heap.size()-1];
heap.pop_back();
int iparent(0),ichildl(1),ichildr(2),ichild;
while (ichildl<heap.size()) {
if (ichildr<heap.size()) ichild=(heap[ichildl]>heap[ichildr]?ichildl:ichildr);
else ichild=ichildl;

if (heap[ichild]>heap[iparent]) swap(heap[ichild], heap[iparent]);
else break;

iparent=ichild;
ichildl=iparent*2+1;
ichildr=iparent*2+2;
}
}
};
``````

The alternative and "lazy":-) solution is to apply the heap container "priority_queue", which will make the code very short and clean!

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> heap;
for (int i(0);i<nums.size();i++) {
heap.push(nums[i]);
}
for (int i(0);i<k-1;i++) heap.pop();
return heap.top();
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.