C++ 算法篇 std::sort_heap

STL堆操作(函数模板)

  • is_heap(v.begin(), v.end())

    检查范围 [first, last) 中的元素是否为最大堆。[c++11]

  • auto heap_end = is_heap_until(v.begin(), v.end());

    检验范围 [first, last) 并寻找始于 first 且为最大堆的最大范围,返回堆的最后一个。[c++11]

  • make_heap(v.begin(), v.end());

    根据区间内的元素创建出一个最大堆 。

    至多 3*N次比较。

  • push_heap(v.begin(), v.end());

    Inserts the element at the position last-1 into the max heap defined by the range [first, last-1).

    如果不是最大堆,不会报错,但是无法生成最大堆。

    进行log(N)次比较。

  • pop_heap(v.begin(), v.end());

    移动最大元素到结尾。

    如果不是最大堆,会报错。

  • sort_heap(v.begin(), v.end());

    转换最大堆 [first, last) 为以升序排序的范围。

    如果不是最大堆,会报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <algorithm>
#include <vector>

int main()
{
std::vector<int> v = { 3, 1, 4, 1, 5, 9 };
std::push_heap(v.begin(), v.end());
std::cout << "heap:\t";
for (const auto &i : v) {
std::cout << i << ' ';
}
std::cout << '\n';

//根据区间内的元素创建出一个最大堆
std::make_heap(v.begin(), v.end()); // 9 5 4 1 1 3

std::cout << "heap:\t";
for (const auto &i : v) {
std::cout << i << ' ';
}
std::cout << '\n';

std::pop_heap(v.begin(), v.end()); // 移动最大元素到结尾

std::cout << "after pop_heap: ";
for (auto i : v) std::cout << i << ' ';// 5 3 4 1 1 9
std::cout << '\n';

int largest = v.back();
v.pop_back(); // 实际移出最大元素
std::cout << "largest element: " << largest << '\n';//9

std::cout << "heap without largest: ";
for (auto i : v) std::cout << i << ' ';// 5 3 4 1 1
std::cout << '\n';

//转换最大堆 [first, last) 为以升序排序的范围,必须保证是最大堆,否则报错。
if (std::is_heap(v.begin(), v.end()))//检查范围 [first, last) 中的元素是否为最大堆。[c++11]
std::sort_heap(v.begin(), v.end());//1 1 3 4 5

std::cout << "\nsorted:\t";
for (const auto &i : v) {
std::cout << i << ' ';
}
std::cout << '\n';

std::make_heap(v.begin(), v.end());
// 很可能扰乱堆
v.push_back(2);
v.push_back(6);

auto heap_end = std::is_heap_until(v.begin(), v.end());

std::cout << "all of v: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';

std::cout << "only heap: ";
for (auto i = v.begin(); i != heap_end; ++i) std::cout << *i << ' ';
std::cout << '\n';

std::push_heap(v.begin(), v.end());
std::cout << "push_heap: ";
for (auto i : v) std::cout << i << ' ';
std::cout << '\n';
}

输出:

1
2
3
4
5
6
7
8
9
heap:   9 1 3 1 5 4
heap: 9 5 4 1 1 3
after pop_heap: 5 3 4 1 1 9
largest element: 9
heap without largest: 5 3 4 1 1
sorted: 1 1 3 4 5
all of v: 5 4 3 1 1 2 6
only heap: 5 4 3 1 1 2
push_heap: 6 4 5 1 1 2 3

using priority_queue

max-heap(default)

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> pq(nums.begin(), nums.end());
for (int i = 0; i < k - 1; i++) {
pq.pop();//将堆顶元素删除k-1次。
}
return pq.top();
}
};

min-heap

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int num : nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
}
};

using multiset(rbt)

min-heap(default)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int> mset;
for (int num : nums) {
mset.insert(num);
if (mset.size() > k) {
mset.erase(mset.begin());//multiset没有pop(),只能用erase(it);
}
}
return *mset.begin();//multiset也没有top(),他是
}
};

max-heap

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
multiset<int, greater<int>> mset(nums.begin(), nums.end());
for (int i = 0; i < k - 1; i++) {
mset.erase(mset.begin());
}
return *mset.begin();
}
};

implements a max-heap

In the above we have presented heap solutions using STL. You may also implement your own heap if you are interested. I suggest you to read the Heapsort chapter of Introduction to Algorithms if you are not familiar with it. The following code implements a max-heap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
buildMaxHeap(nums);
for (int i = 0; i < k - 1; i++) {
swap(nums[0], nums[--heapSize]);
maxHeapify(nums, 0);
}
return nums[0];
}
private:
int heapSize;

int left(int i) {
return (i << 1) + 1;
}

int right(int i) {
return (i << 1) + 2;
}

void maxHeapify(vector<int>& nums, int i) {
int largest = i, l = left(i), r = right(i);
if (l < heapSize && nums[l] > nums[largest]) {
largest = l;
}
if (r < heapSize && nums[r] > nums[largest]) {
largest = r;
}
if (largest != i) {
swap(nums[i], nums[largest]);
maxHeapify(nums, largest);//递归
}
}

void buildMaxHeap(vector<int>& nums) {
heapSize = nums.size();
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
maxHeapify(nums, i);
}
}
};

REF

最大堆(创建、删除、插入和堆排序)

Thanks for Support.