C++实现小根堆(再版)+Graphviz和DOT语言绘图

2019-03-13 本文已影响12人 _小李没有刀_

为什么是再版？

因为觉得CSDN的版面不好看、广告太多，所以来到简书。想把之前的内容搬过来，虽然不多，但还是放在一个地方的好。最近看到了一个程序员画图的好东西——使用Graphviz和DOT语言绘图，瞬间觉得自己以前在draw.io上搞了半天整个图太low了，不如直接dot文件描述图是怎么样的，然后终端一行dot -Tpng heap.dot -o heap.png直接生成来的快。生搬有点尬，所以想重构一下，主要是改两点：

换成C++实现小根堆
使用Graphviz和DOT语言绘图

之前是用Java实现的，现在看了看觉得写的不好，所以准备用C++写，但代码逻辑几乎是一样的。
最后，原文链接——Java实现的小根堆

1、二叉堆

首先参考了一下 $\rightarrow$ 什么是二叉堆？此博客也是在看了这篇微信推文的基础上写的。

什么是二叉堆？

二叉堆本质上是一种完全二叉树，它分为两个类型：
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;]
}