Created
October 30, 2017 12:27
-
-
Save zhouhoo/4a6970239572d79040ebbbfe70b605dc to your computer and use it in GitHub Desktop.
build max heap to find kth largest num
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| class Solution { | |
| public: | |
| inline int left(int idx) { | |
| return (idx << 1) + 1; | |
| } | |
| inline int right(int idx) { | |
| return (idx << 1) + 2; | |
| } | |
| void max_heapify(vector<int>& nums, int idx) { | |
| int largest = idx; | |
| int l = left(idx), r = right(idx); | |
| if (l < heap_size && nums[l] > nums[largest]) largest = l; | |
| if (r < heap_size && nums[r] > nums[largest]) largest = r; | |
| if (largest != idx) { | |
| swap(nums[idx], nums[largest]); | |
| max_heapify(nums, largest); | |
| } | |
| } | |
| void build_max_heap(vector<int>& nums) { | |
| heap_size = nums.size(); | |
| for (int i = (heap_size >> 1) - 1; i >= 0; i--) | |
| max_heapify(nums, i); | |
| } | |
| int findKthLargest(vector<int>& nums, int k) { | |
| build_max_heap(nums); | |
| for (int i = 0; i < k; i++) { | |
| swap(nums[0], nums[heap_size - 1]); | |
| heap_size--; | |
| max_heapify(nums, 0); | |
| } | |
| return nums[heap_size]; | |
| } | |
| private: | |
| int heap_size; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment