为什么是再版？
因为觉得CSDN的版面不好看、广告太多，所以来到简书。想把之前的内容搬过来，虽然不多，但还是放在一个地方的好。最近看到了一个程序员画图的好东西——使用Graphviz和DOT语言绘图，瞬间觉得自己以前在draw.io上搞了半天整个图太low了，不如直接dot文件描述图是怎么样的，然后终端一行dot -Tpng heap.dot -o heap.png直接生成来的快。生搬有点尬，所以想重构一下，主要是改两点：
- 换成C++实现小根堆
- 使用Graphviz和DOT语言绘图
之前是用Java实现的，现在看了看觉得写的不好，所以准备用C++写，但代码逻辑几乎是一样的。
最后，原文链接——Java实现的小根堆
1、二叉堆
首先参考了一下什么是二叉堆？ 此博客也是在看了这篇微信推文的基础上写的。
什么是二叉堆？
二叉堆本质上是一种完全二叉树，它分为两个类型：
1.最大堆
2.最小堆
什么是最大堆呢？最大堆任何一个父节点的值，都大于等于它左右孩子节点的值。
什么是最小堆呢？最小堆任何一个父节点的值，都小于等于它左右孩子节点的值。
二叉堆的根节点叫做堆顶。
最大堆和最小堆的特点，决定了在最大堆中，堆顶是整个堆中的最大元素；最小堆中，堆顶是整个堆中的最小元素。
2、一个例子
一个二叉堆的操作大致有三种，
1. 调整堆
2. 插入元素
3. 取出堆顶元素
假设给我的一串数字是：【10 2 4 21 15 13 18 7 11】 ，即：
int a[] = {10,2,4,21,15,13,18,7,11};
下面过一遍堆的调整、插入和取出。 提醒一点，向上调整只比较一次，向下调整比较两次。 下面会有提到。
2.1 生成完全二叉树：
对于任何一个序列，我们所需要做的是先把它当作一颗完全二叉树，就是下面这样子。
原序列转成完全图 这里注意是用数组存的
2.2、调整为小根堆
堆调整是向下调整 ，从后往前依次调整每棵子树，每次调整时需要比较两次，子节点之间一次，较小的（对小根堆来说）子节点和根节点之间一次。
1. 向上调整
先在最后一颗子树上调整：
最后一颗子树
比较子节点。7 更小一点。
7和11比较
7胜出
于是7 和21 比较，发现7 比21 更小。调换两个节点的值。
21和7比较
7胜出并交换节点顺序
往上，调整前一颗子树【4 13 18】。比较子节点，13与18比较，13小。13再与4比较，4小。于是此子树也不需要做调整。
13和18比较且13获胜
4与13比较，4获胜并上调
再往上，比较【2 7 15】这颗子树，同理还是无需调整。
无需调整
再往上，比较【10 2 4】这颗子树，2 较小，然后2 与10 比较。
再到2和4比较，2小
2与10比较，2小要上调
接下来就是2和10交换，交换之后开始向下调整。
2. 向下调整
把10换下来。同理，7与10比较。
7与10比较，7小
这里插一段上面图的代码
digraph G{
size = "4,4";
node [color = Tan,style = filled];
subgraph cluster1{
bgcolor = mintcream;
7[color = pink];
10[color = pink];
}
//{rank = same;2}
2 -> {10 4};
4 -> {13 18};
10 -> 7 -> {21 11};
10 -> 15;
2[shape = doublecircle;]
}
保存为.dot，如heap.dot，切到相应路径，终端输入
dot -Tpng heap.dot -o heap.png即可得到heap.png。具体可查看doc
接下来的调整以及节点的插入和取堆顶元素就不接着说了，我的这篇Java实现的小根堆里有，这里调整好的图是：
调整的图
2.3 代码
#include <iostream>
#include <vector>
using namespace std;
class heapOperator{
private:
vector<int> heap;
public:
// 构造函数，用一个数组初始化堆
heapOperator(const vector<int>& h){
for(auto item: h){
heap.push_back(item);
}
// 数组调整为堆
heapSort();
}
heapOperator(){
//heapInsert(<#const int &i#>)
}
// 堆调整
void heapSort();
// 堆插入
void insert(const int& i);
// 直接取走元素，根据需要也可返回
void fetch();
void print(){
//cout << "生成的小根堆为: ";
for(auto item: heap){
cout << item << " ";
}
cout << endl;
}
};
void heapOperator::heapSort(){
// 这里是为了不产生警告，换成int也没太大关系
long len = heap.size();
long root = len / 2;
// 最后一个根节点可能只有一个子节点，可以少比较一次
if (len % 2 == 0) {
if(heap[root - 1] > heap[len - 1]){
swap(heap[root - 1],heap[len - 1]);
}
}
while (root > 0) {
// k一直跟着当前的节点，直到此节点被换到叶子结点上
long k = root;
// len/2 - 1是第一个叶节点的下标
// 每次向上调整后都还要向下调整，不然就错了
while (k <= len / 2) {
// 左子节点在数组中的下标
long lNode = 2 * k - 1;
// 右子节点在数组中的下标
long rNode = 2 * k;
// 如果左子节点小于等于右子节点
if(heap[lNode] <= heap[rNode]){
// 同时左子节点小于父节点
if (heap[lNode] < heap[k - 1]) {
swap(heap[lNode], heap[k - 1]);
// 记下此节点是数组中第几个值
k = 2 * k;
}
// 如果父节点不小于最小的子节点的值 跳出循环
else {
break;
}
// 若右节点更小一点
} else {
// 如果右子节点小于父节点
if (heap[rNode] < heap[k - 1]) {
swap(heap[rNode], heap[k - 1]);
// 记下此节点是数组中第几个值
k = 2 * k + 1;
}
// 如果父节点不小于最小的子节点的值 跳出循环
else {
break;
}
}
}
--root;
}
}
void heapOperator::insert(const int& i){
heap.push_back(i);
// 向上比较
long len = heap.size();
long k = len, root = len / 2;
// root代表第几个元素，最起码是第一个元素,len = 1情况也随之排除
while (root > 0) {
if (heap[root - 1] > heap[k - 1]) {
swap(heap[root - 1], heap[k - 1]);
k = root;
root /= 2;
} else{
return;
}
}
}
void heapOperator::fetch(){
// cout << "已取走最小的元素" << heap[0] << endl;
swap(heap[0], heap[heap.size() - 1]);
heap.erase(heap.end() - 1);
// 向下调整
long root = 1, len = heap.size();
do {
long lNode = 2 * root - 1, rNode = 2 * root;
// 如果左子节点小于等于右子节点
if (heap[lNode] <= heap[rNode]) {
// 同时左子节点小于父节点
if (heap[lNode] < heap[root - 1]) {
swap(heap[lNode], heap[root - 1]);
// 记下此节点是数组中第几个值
root = 2 * root;
}
// 如果父节点不小于最小的子节点的值 跳出循环
else {
break;
}
// 若右节点更小一点
} else {
// 如果右子节点小于父节点
if (heap[rNode] < heap[root - 1]) {
swap(heap[rNode], heap[root - 1]);
// 记下此节点是数组中第几个值
root = 2 * root + 1;
}
// 如果父节点不小于最小的子节点的值 跳出循环
else {
break;
}
}
} while (root <= len / 2);
}
int main(){
int a[] = {10,2,4,21,15,13,18,7,11};
vector<int> aa(a, a+9);
heapOperator minHeap(aa), testHeap;
// 打印一下minHeap
cout << "打印一下minHeap: ";
minHeap.print();
// 往minHeap插入1
minHeap.insert(1);
cout << "打印一下minHeap: ";
minHeap.print();
// 测试一下能不能直接插入元素
testHeap.insert(10);
testHeap.insert(2);
// 打印一下testHeap
cout << "打印一下testHeap: ";
testHeap.print();
testHeap.insert(3);
cout << "打印一下testHeap: ";
testHeap.print();
//删除两个堆的堆顶元素并打印
minHeap.fetch();
testHeap.fetch();
cout << "minHeap: ";
minHeap.print();
cout << "testHeap: ";
testHeap.print();
return 0;
}
运行结果：
打印一下minHeap: 2 7 4 10 15 13 18 21 11
打印一下minHeap: 1 2 4 10 7 13 18 21 11 15
打印一下testHeap: 2 10
打印一下testHeap: 2 10 3
minHeap: 2 7 4 10 15 13 18 21 11
testHeap: 2 10
Program ended with exit code: 0
3.总结
- 堆这种数据结构还是比较基础的，用处也比较大。比如堆排序，它是一个能在时间O(nlogn)时间排序的算法。堆的插入和删除都是O(logn)时间的，对于频繁删除和插入元素是比较支持的。
- 对于Graphviz和DOT语言绘图，我觉得还是挺好用的，一种好用的东西一开始用都觉得各种不对、各种不会，然后摸索。我写这篇也是，从一开始的图到最后的图，虽然我几乎只是用到了皮毛，但图的变化还是看的到一点点的，用了好几个小时，不一定比上次花的时间少，但我学了点东西，这东西的好处是还可以和Java的Runtime.getruntime一起使用（这个我用过），文档里也说它可以作为库和perl、C++、python可以一起用，感兴趣的可以和我分享一下哈，我也不会～
-
留个问题给路过的大佬！怎么给cluster指定位置呢，我其中有张图没有加框，是因为加框是subgraph的操作，我每次给【4 18 13】一加子图，节点4和节点10的位置就互调了，我找了很多解决方法都不行，希望路过的大佬能指点一下，提前谢谢您～
下面插张图，您就清楚了。
4应该是2的右节点
代码：
digraph G{
size = "4,4";
node [color = Tan,style = filled];
subgraph cluster1{
bgcolor = mintcream;
4;
18[color = pink];
13[color = pink];
}
//{rank = same;2}
2 -> {10 4};
4 -> {13 18};
10 -> 7 -> {21 11};
10 -> 15;
2[shape = doublecircle;]
}
网友评论