# 4ms c++ code use heap sort

• code is simple
1 create a small heap with size k
2 for data between [k-1,size-1], check and modify the heap
3 at last the heap top data is the K'th largest one.

``````class Solution {
void modifyHeap(vector<int>& nums, int index, int k)
{
int lc = 2*index+1;
int rc = lc+1;
if(lc>=k) return;

int minv = nums[index];
int minindex = index;
if(lc<k && nums[lc]<minv)
{
minv = nums[lc];
minindex = lc;
}
if(rc<k && nums[rc]<minv)
{
minv = nums[rc];
minindex = rc;
}
if(minindex!=index)
{
swap(nums[minindex],nums[index]);
modifyHeap(nums,minindex,k);
}
}
void buildHeap(vector<int>& nums, int k)
{
int x = k/2-1;
for(int i = x;i>=0;--i)
{
modifyHeap(nums,i,k);
}
}
public:
int findKthLargest(vector<int>& nums, int k) {
int size ;
if((size=nums.size()) == 0) return 0;
if(size == 1)return nums[0];
buildHeap(nums,k);
for(int i = k;i<size;++i)
{
if(nums[i]>nums[0])
{
swap(nums[i],nums[0]);
modifyHeap(nums,0,k);
}

}

return nums[0];

}
};``````

• you can directly use make_heap, pop_heap and push_heap routines in c++ stl.

• std::priority_queue<int, std::vector<int>, std::greater<int>> is min heap which stores integer.

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