前几天翻了一下之前的代码,感觉模板类看着好难受(并且写的不是很好),所以重写了一遍。

#include <iostream>
#include <vector>
#include <queue>
#include <ctime>
#include <cmath>
using namespace std;

class heap
{
private:
    /*存放数据*/
    vector<int> value;

    /*调整节点位置*/
    void siftdown(int i);
    void siftup(int i);
    void adjust();

public:
    /*构造 && 析构*/
    heap() { value.resize(1); }//编号为0的空间是不用的
    ~heap() {    }

    /*创建 && 插入*/
    void create(int a[], const int &n);
    void create(const vector<int> &n);
    void insert(const int &v);

    /*删除 && 清空*/
    void clear() { value.clear(); }
    int pop_front();
    bool erase(const int &pos);

    /*堆信息*/
    bool empty() { return value.empty(); }
    int size() { return value.size() - 1; }
    int top_value() { return value[1]; }

    /*查找*/
    int find(const int &v);

    /*排序*/
    void sort(int res[]);
    void sort(vector<int> &res);

    /*其它*/
    void travel();
};

/*****************************************************************
Function:siftdown
Description:将一个节点向下调整。
*****************************************************************/

inline void heap::siftdown(int i)
{//传入一个需要调整的节点
    int n = value.size();
    int min_pos = i;//min_pos用来判断是否需要继续循环
    bool flag = true;//flag用来记录是否继续循环

    while (i * 2 < n && flag)
    {//在第i个节点有左儿子且需要继续调整的时候循环。
        min_pos = value[i * 2] < value[i] ? i * 2 : i;
        //判断父亲和左儿子的关系

        if (i * 2 + 1 < n)//判断右儿子(如果有的话)
            if (value[i * 2 + 1] < value[i])
                min_pos = i * 2 + 1;

        if (min_pos == i)//不需要改变了
            flag = false;
        else //有比父节点还小的子节点,交换
        {
            int tmp = value[min_pos];
            value[min_pos] = value[i];
            value[i] = tmp;

            i = min_pos;//更新 i,方便继续调整
        }
    }

    return;
}

/*****************************************************************
Function:siftup
Description:将一个节点向上调整。
*****************************************************************/

inline void heap::siftup(int i)
{
    bool flag = true; //是否需要调整的标志

    while (flag)
    {
        if (i == 1)//如果达到堆顶了
            return;

        if (value[i] < value[i / 2])
        { //如果子节点比父节点小,交换
            int tmp = value[i];
            value[i] = value[i / 2];
            value[i / 2] = tmp;
        }
        else
            flag = false;

        i /= 2;//方便后面调整
    }

    return;
}

/*****************************************************************
Function:adjust
Description:将数组调整成堆。
*****************************************************************/

inline void heap::adjust()
{
    for (int i = value.size() / 2; i > 0; i--)
        siftdown(i);//从最后一个非叶节点开始调整

    return;
}

/*****************************************************************
Function:create
Description:创建一个堆。
*****************************************************************/

inline void heap::create(int a[], const int & n)
{
    for (int i = 0; i < n; i++)
        value.push_back(a[i]);

    adjust();//插入后调整位置
}

inline void heap::create(const vector<int>& n)
{
    value = n;
    adjust();

    return;
}

/*****************************************************************
Function:insert
Description:将一个节点插入到堆里。
*****************************************************************/

inline void heap::insert(const int & v)
{
    value.push_back(v);//将数据插入

    siftup(value.size() - 1);//再调整位置

    return;
}

/*****************************************************************
Function:pop_front
Description:删除堆顶。
*****************************************************************/

inline int heap::pop_front()
{
    int tmp = value[1];

    erase(1);

    return tmp;
}

/*****************************************************************
Function:erase
Description:将一个节点删除。
*****************************************************************/

inline bool heap::erase(const int & pos)
{
    if (pos > 0 && pos < value.size())
    {//在范围内才执行删除
        value[pos] = value[value.size() - 1];

        value.pop_back();
        siftdown(pos);

        return true;
    }

    return false;
}

/*****************************************************************
Function:find
Description:查找一个节点,返回其位置。
*****************************************************************/

inline int heap::find(const int & v)
{//利用广搜思想来查找
    if (empty())//判空
        return 0;

    queue<int> q;
    q.push(1);

    while (!q.empty())
    {//运用队列遍历堆
        int tmp = q.front();

        q.pop();

        if (value[tmp] == v)
            return tmp;//找到就返回位置

        if (value[tmp] > v)//最小值都比要查找的值大
            continue;//下面也没必要执行了

        /*判断左右儿子是否存在,存在就加入队列*/
        if (tmp * 2 < value.size())
            q.push(tmp * 2);

        if (tmp * 2 + 1 < value.size())
            q.push(tmp * 2 + 1);
    }

    return 0;
}

/*****************************************************************
Function:sort
Description:堆排序。
*****************************************************************/

inline void heap::sort(int res[])
{
    heap tmp = *this;
    int cnt = 0;
    clock_t begin, end;

    begin = clock();

    while (!tmp.empty())
        res[cnt++] = tmp.pop_front();

    end = clock();

    cout << "Used time = " << (double)(end - begin) / CLOCKS_PER_SEC << " s" << endl;

    return;
}

inline void heap::sort(vector<int>& res)
{
    res.clear();

    heap tmp = *this;
    int cnt = 0;
    clock_t begin, end;

    begin = clock();

    while (!tmp.empty())
        res.push_back(tmp.pop_front());

    end = clock();

    cout << "Used time = " << (double)(end - begin) / CLOCKS_PER_SEC << " s" << endl;

    return;
}

/*****************************************************************
Function:travel
Description:输出堆。
*****************************************************************/

inline void heap::travel()
{
     cout << "The elements in this heap is :" << endl;

    for (int i = 1; i < value.size(); i++)
        cout << value[i] << " ";

    cout << endl;

    return;
}

树状输出实在懒得写了,想写可以自己写吧。

Last modification:April 8th, 2019 at 10:18 am
If you think my article is useful to you, please feel free to appreciate