# C++那些事之手写二叉堆强化模板及比较操作

https://github.com/Light-City/CPlusPlusThings

## 1.Heap实现

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);
}
};
};
1. 子结点与父结点

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操作

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--;
}
}
1. 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;
}
1. Pop操作

void Pop() {
swap(0,data_.size()-1);
data_.pop_back();
SiftDown(0);
}
1. Push操作

void Push(T value) {
data_.push_back(value);
SiftUp(data_.size() - 1);
}
1. SiftUp操作

void SiftUp(int k) {
while (k > 0 && cmp(data_[k], data_[GetParent(k)])) {
int p = GetParent(k);
swap(p,k);
k = p;
}
}
1. Top操作

T Top() {
assert(data_.size() > 0);
return data_[0];
}
1. 其他常用操作

int GetSize() {
return data_.size();
}
void GetData(vector<T> &data) {
data = data_;
}
bool Empty() {
return data_.empty();
}

## 2.优先队列

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();
}
};
};

## 3.测试

### 3.1 Heap测试

Heap小根堆例子：

5
4    6
0  10

0
4   6
5 10

push -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  4

push 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 优先队列测试

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;
}
};

0 条评论

• ### 机器学习之数据之美

昨天看了一下机器学习的东西，发现在做特征工程时，需要用到seaborn的可视化方法。

• ### Hive SQL开窗函数实战

开窗函数是数据的一种查询统计语法糖，多是用于离线统计，这同时也是大数据技术栈的应用场景。今天学习Hive SQL的开窗(窗口)函数，对比与MySQL，在MySQ...

• ### 回归Android，继续刷题

这两天要做个安卓项目，哎，我之前是做安卓开发的，做了半年多，后面就没做了，距离现在至少1年半有余。

• ### 小顶堆Java实现

参考文章： 漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析 http://blog.csdn.net/touch_2011/article/detai...

• ### Python与Tableau相结合，万字长文搞定传统线下连锁店数据分析

这是kaggle上的一份巴西传统线下汽车服务类连锁店的实际销售数据，大小约3.43G，包含了从2017年3月31日到2020年4月1日大约2600万多的销售数据...

• ### 使用GAN生成序列数据

【导读】序列数据十分常见，但由于隐私，法规限制了对有用数据的访问，这极大地减慢了对研发至关重要的有用数据的访问。因此产生了对具有高度代表性但又完全私有的合成序...

• ### 05-树7 堆中的路径 (25分)

将一系列给定数字插入一个初始为空的小顶堆H[]。随后对任意给定的下标i，打印从H[i]到根结点的路径。

• ### Python算法题----列表去重

有这样一个列表[1, 1, 1, 2, 3, 3, 2, 4, 3, 4, 5, 5, 5, 6, 7, 8, 9, 9, 9, 9, 10, 10], 写一个...