# MinHeap and QuickSelect

• 1 Sorting
Time Complexity: worst O(nlogn)
The naive way is to sorting entire array and select the desired entry.

2 MinHeap
Time Complexity: worst O(nlogk)
Run Time: 4ms

``````int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int> > pq;
int i;
for (i = 0; i < k; i++) {
pq.push(nums[i]);
}

for (i = k; i < nums.size(); i++) {
pq.push(nums[i]);
pq.pop();
}

return pq.top();
}
``````

When thinking about a problem, I would always first consider if any built-in data structure may help in the problem
The "kth element" indicates the element would be "smallest in k elements". Here MinHeap naturally comes up. So we just need to maintain a pq with k elments all the time and at last return the top one.

3 QuickSelect
Time Complexity: average O(n) worst case O(n ^ 2)
Run Time: 36ms

``````int findKthLargest(vector<int>& nums, int k) {
return recursion(nums, nums.size() + 1 - k, 0, nums.size() - 1);
}

int recursion(vector<int>& nums, int k, int start, int end) {
if (start == end) return nums[start];

int pivot = partition(nums, start, end);
int order = pivot - start + 1;

if (order == k) return nums[pivot];
if (order > k) return recursion(nums, k, start, pivot - 1);
else return recursion(nums, (k - order), pivot + 1, end);
}

int partition(vector<int>& nums, int start, int end) {
if (start == end) return start;
int p = nums[start];
int i = start + 1, j = end;
while (i <= j) {
if (nums[i] <= p) {
i++;
} else if (nums[j] > p) {
j--;
} else {
swap(nums[i++], nums[j--]);
}
}

swap(nums[start], nums[j]);
return j;
}
``````

Just use quickselect, which is same idea of QuickSort. Be careful about two points:

1. partition function returns the index of pivot, not order statics. We should transform it and then compare with k.
2. the problem says kth largest, tradition paritition gets smallest something.

The quickselect is slower than MinHeap in the Submission Runtime. I think it is due to my stupid parition

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