C++那些事之手写二叉堆强化模板函数及比较操作
C++那些事之手写二叉堆强化模板函数及比较操作
C++那些事之手写二叉堆强化模板及比较操作
强化算法、熟练C++
本节重点带大家一起写一个二叉堆，并基于二叉堆实现优先队列，同时练习C++的模板类以及比较操作。
本文的代码后续会放在《C++那些事》仓库中，请持续关注！
https://github.com/Light-City/CPlusPlusThings
1.Heap实现
类模板，二叉堆中需要元素进行比较，二叉堆分为大顶堆与小顶堆，我们通过模板实现支持多种元素类型且支持两种堆的一个Heap类。
在C++中实现，就是下面的模板类，T代表元素类型，Cmp代表可比较对象，我们默认以less，也就是在下面我们将支持默认的小根堆，如果想要支持大根堆，自己传入一个比较对象即可，后面一步步来阐述。
namespace lightcity {
template<typename T,typename Cmp = std::less<T>>
class Heap {
private:
vector<T> data_;
Cmp cmp;
public:
Heap() {}
Heap(T capacity) {
data_ = vector<T>(capacity);
}
};
};- 子结点与父结点
二叉堆这里实现我们以vector作为底层，我们数组的index范围为0~index-1。
堆顶就是0。左孩子是1，右孩子是2，依次类推。
我们需要直到当前结点的左孩子与右孩子，父亲是谁？
int GetParent(int child) {
assert(child > 0);
return (child - 1)/2;
}
int GetLeftChild(int parent) {
return 2*parent + 1;
}
int GetRightChild(int parent) {
return 2*parent + 2;
}2）Heapify操作
给定一个数组，将数组转为二叉堆(大或小根堆)。
具体实现：从最后一个非叶结点开始，依次向上直到根结点，进行siftdown操作，也就是下沉操作，这样做的目的是，以小根堆为例：当非叶子结点比后面两个孩子大，我们就需要将孩子中最小的结点与之交换，使得满足小根堆性质。
Heap(vector<T>& heap) {
data_ = heap;
T last_not_leaf = GetParent(data_.size() - 1);
while (last_not_leaf >= 0) {
SiftDown(last_not_leaf);
last_not_leaf--;
}
}- SiftDown操作
将非叶子结点下沉，使得满足二叉堆性质。
void SiftDown(int k) {
while (GetLeftChild(k) < data_.size()) {
int j = GetLeftChild(k);
if (j + 1 < data_.size() && cmp(data_[j + 1],data_[j]))
j =GetRightChild(k); //j++
// data[j]是此时leftChild 和 rightChild中的最大值
if (cmp(data_[k],data_[j])) break;
swap(k, j);
k = j;
}
}swap操作：
void swap(int i, int j) {
T t = data_[i];
data_[i] = data_[j];
data_[j] = t;
}- Pop操作
通过pop操作，我们将堆顶元素删除，具体操作如下：
堆顶与最后一个叶子结点交换，此时最后一个元素便是堆顶，将其删除即可，堆堆顶元素进行SiftDown操作，使其满足二叉堆性质。
void Pop() {
swap(0,data_.size()-1);
data_.pop_back();
SiftDown(0);
}- Push操作
通过Push操作，往堆中添加元素，具体操作如下：
直接将元素在数组尾巴插入，随后从刚才插入的结点开始进行进行SiftUp操作，使得满足二叉堆性质。
void Push(T value) {
data_.push_back(value);
SiftUp(data_.size() - 1);
}- SiftUp操作
将元素进行上浮，使得满足二叉堆性质，例如：当前叶子结点是10父亲结点时8，此时不满足大根堆性质，我们就需要交换两者，不断往上，直到当前结点比父亲结点小。
void SiftUp(int k) {
while (k > 0 && cmp(data_[k], data_[GetParent(k)])) {
int p = GetParent(k);
swap(p,k);
k = p;
}
}- Top操作
为了方便拿到最大或者最小元素，提供Top接口：
T Top() {
assert(data_.size() > 0);
return data_[0];
}- 其他常用操作
最后，就是一些其他的常见操作，例如：元素个数、是否为空等.
int GetSize() {
return data_.size();
}
void GetData(vector<T> &data) {
data = data_;
}
bool Empty() {
return data_.empty();
}2.优先队列
接着，我们以上述实现的Heap来实现一个优先队列：
namespace lightcity {
template<typename T,typename Cmp = std::less<T>>
class priority_queue {
private:
Heap<T, Cmp> heap;
public:
priority_queue() {}
int GetSize() {
return heap.GetSize();
}
void Push(T value) {
heap.Push(value);
}
T Top() {
return heap.Top();
}
void Pop() {
heap.Pop();
}
bool Empty() {
return heap.Empty();
}
};
};实现简单的很，我们方法都模拟真实的STL中的函数，开头改为大写，记得加namespace，否则编译器模糊不知道调用哪一个。
3.测试
3.1 Heap测试
Heap小根堆例子：
5
4 6
0 10小根堆：
0
4 6
5 10push -1
0
4 6
5 10 -1调整：
-1
4 0
5 10 6测试输出：
小根堆
0 4 6 5 10
push
-1 4 0 5 10 6 Heap大根堆例子：
5
4 6
0 10调整堆后：
10
5 6
0 4push 100：
10
5 6
0 4 100调整堆后：
100
5 10
0 4 6输出：
大根堆
10 5 6 0 4
push
100 5 10 0 4 6 对应代码：
void HeapTest(bool flag = true) {
vector<int> data{5,4,6,0,10};
using namespace lightcity;
if (flag) {
cout << "小根堆" << endl;
Heap<int,CmpMin> heap(data);
heap.GetData(data);
for (const auto& elem : data)
cout << elem << " ";
cout << endl;
cout << "push" << endl;
heap.Push(-1);
heap.GetData(data);
for (const auto& elem : data)
cout << elem << " ";
cout << endl;
} else {
cout << "大根堆" << endl;
Heap<int,CmpMax> heap(data);
heap.GetData(data);
for (const auto& elem : data)
cout << elem << " ";
cout << endl;
cout << "push" << endl;
heap.Push(100);
heap.GetData(data);
for (const auto& elem : data)
cout << elem << " ";
cout << endl;
}
}3.2 优先队列测试
我们以leetcode347 topk题目测试：
using namespace lightcity;
using pii = pair<int,int>;
class cmp {
public:
bool operator ()(const pii& a,const pii& b) {
return a.first<b.first;
}
};
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pii,cmp> pq;
unordered_map<int,int> um;
for (auto& num : nums) um[num]++;
for (auto& elem : um) {
if (k>0) {
pq.Push(make_pair(elem.second,elem.first));
k--;
} else if (elem.second > pq.Top().first) {
pq.Pop();
pq.Push(make_pair(elem.second,elem.first));
}
}
vector<int> res;
while(!pq.Empty()) {
res.push_back(pq.Top().second);
pq.Pop();
}
return res;
}
};提交后AC!
本节完