使用Max Heap解决“数个数字”的时间复杂性是多少。问题？
“查找数组中的第三个数字”问题：
inputs: [3,2,1,5,6,4], k = 2
outputs: 5
inputs: [3,2,3,1,2,4,5,5,6], k = 4
outputs: 4
我知道可以使用快速选择和min heap算法将此问题宣布。但是，我在这里关注的是使用Max Heap。步骤如下：
1. Build max heap form the whole given array, inplace.
2. Iterate k times. In each iteration, Take and remove the heap top.
3. The last heap top taken at the k-th iteration is the result.
以下是CPP中的代码：
void swap(vector<int>& nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
void heapify_down(vector<int>& nums, int parent_idx, int end_idx) {
int left_idx = parent_idx * 2 + 1, right_idx = left_idx + 1;
while (left_idx <= end_idx) {
int largeset_idx = parent_idx;
if (nums[left_idx] > nums[largeset_idx]) largeset_idx = left_idx;
if (right_idx <= end_idx && nums[right_idx] > nums[largeset_idx]) largeset_idx = right_idx;
if (largeset_idx != parent_idx) {
swap(nums, parent_idx, largeset_idx);
parent_idx = largeset_idx;
left_idx = parent_idx * 2 + 1;
right_idx = left_idx + 1;
}
else {
return ;
}
}
}
void build_heap(vector<int>& nums) {
for (int i = nums.size() - 1; i >= 0; i--) heapify_down(nums, i, nums.size() - 1);
}
int findKthLargest(vector<int>& nums, int k) {
build_heap(nums);
int cnt = 0, res, cur_end = nums.size() - 1;
while (cnt != k) {
res = nums[0];
cnt += 1;
swap(nums, 0, cur_end);
cur_end -= 1;
heapify_down(nums, 0, cur_end);
}
return res;
}
此方法的时间是什么？我在第一步中使用自下而上的方法，此步骤应为o（n）。但是，循环使我感到困惑。循环执行k次，每个循环将调用heapify_down是o（log（log（n））comlexity。那么总体复杂性o（n + k * log（n））= o（max（n，k * log（n）））？如果我错了，请纠正我。
"Find the K-th largest number in the array" problem:
inputs: [3,2,1,5,6,4], k = 2
outputs: 5
inputs: [3,2,3,1,2,4,5,5,6], k = 4
outputs: 4
I know that this problem can be soleved with quick select and min heap algorithms. However, what I'm focusing here is using max heap. The steps is the following:
1. Build max heap form the whole given array, inplace.
2. Iterate k times. In each iteration, Take and remove the heap top.
3. The last heap top taken at the k-th iteration is the result.
Below is the code in cpp:
void swap(vector<int>& nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
void heapify_down(vector<int>& nums, int parent_idx, int end_idx) {
int left_idx = parent_idx * 2 + 1, right_idx = left_idx + 1;
while (left_idx <= end_idx) {
int largeset_idx = parent_idx;
if (nums[left_idx] > nums[largeset_idx]) largeset_idx = left_idx;
if (right_idx <= end_idx && nums[right_idx] > nums[largeset_idx]) largeset_idx = right_idx;
if (largeset_idx != parent_idx) {
swap(nums, parent_idx, largeset_idx);
parent_idx = largeset_idx;
left_idx = parent_idx * 2 + 1;
right_idx = left_idx + 1;
}
else {
return ;
}
}
}
void build_heap(vector<int>& nums) {
for (int i = nums.size() - 1; i >= 0; i--) heapify_down(nums, i, nums.size() - 1);
}
int findKthLargest(vector<int>& nums, int k) {
build_heap(nums);
int cnt = 0, res, cur_end = nums.size() - 1;
while (cnt != k) {
res = nums[0];
cnt += 1;
swap(nums, 0, cur_end);
cur_end -= 1;
heapify_down(nums, 0, cur_end);
}
return res;
}
What is the time complextity of this method? I'm using bottom-up approach in the first step, this step should be O(n). However, the while loop makes me confused. The loop execute k times, each loop will call heapify_down which is O(log(n)) comlexity. So is the overall complexity O(n + k * log(n)) = O(max(n, k * log(n)))? Correct me if I'm wrong.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果您正确地做，则建造堆是
o（n），并且删除顶部是o（log n），并且使用k是取消结合可能是n。因此，总体而言，它是
o（n + k * log n）== o（n + n * log n）== o（n log n）。您没有更多信息，例如
k＆lt; log n还是什么？构建堆时，请勿使用
heapify_down，因为这会导致O（n * log n）。相反，如果堆的大小奇数，则首先忽略最后一个元素。然后从i = size/2-1开始，然后交换i，2 * i和2 * i + 1周围最大的是i。重复直到i - = 0。如果大小为奇数，则将最后一个元素添加到堆中。Building a heap, if you do it right, is
O(n)and removing the top isO(log n)and withkbeing unbound it could ben.So overall it is
O(n + k * log n) == O(n + n * log n) == O(n log n).Don't you have some more information, like
k < log nor something?When building your heap don't use
heapify_down, because that results in O(n * log n). Instead first ignore the last element if the heap has odd size. Then start ati = size / 2 - 1and swapi,2 * iand2 * i + 1around so the largest is ati. Repeat tilli-- = 0. If the size was odd add the last element to the heap.