编程开发中如何实现堆

这篇文章主要介绍了编程开发中如何实现堆，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

一、堆的概念

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树结构。

堆结构的二叉树存储是：

最大堆：每个父节点的都大于孩子节点。

最小堆：每个父节点的都小于孩子节点。

堆栈中的物体具有一个特性： 最后一个放入堆栈中的物体总是被最先拿出来， 这个特性通常称为后进先出(LIFO)队列。 堆栈中定义了一些操作。 两个最重要的是PUSH和POP。 PUSH操作在堆栈的顶部加入一 个元素。POP操作相反， 在堆栈顶部移去一个元素， 并将堆栈的大小减一。

在此，用vector容器来实现存储，vector容器是一个模板类，可以存放任何类型的对象（但必须是同一类对象）。vector对象可以在运行时高效地添加元素，并且vector中元素是连续存储的。当容量不够时，它能够自己去扩容。故我们在push数据时就不用考虑一些其他容量不足等等因素。

二、堆的实现

通过二叉树来实现堆的结构。

先实现一个compare，如果实现大小堆用对象调其对应类运算符"（）"重载

templatestruct Less{        bool operator()(const T& l, const T& r)        {                return l < r;        }};templatestruct Big{        bool operator()(const T& l, const T& r)        {                return l > r;        }};

先定义一个堆：

用模板的模板参数：

如：当 测试用例为：

int arr[] = { 12, 10, 43, 23, 22, 45, 67,9 };

Heap N(arr, sizeof(arr)/sizeof(arr[0]));

当你给定compare为Big时它会按照大堆去排序

Heap N(arr, sizeof(arr)/sizeof(arr[0]));

当你给定compare为Big时它会按照小堆去排序

template  class compare >  //模板的模板参数class Heap{public:        Heap()        {}        Heap(T* a, size_t size)        {                _a.reserve(size);                for (size_t i = 0; i < size; ++i)                {                        _a.push_back(a[i]);                }                //建堆                                for (int i = (_a.size() -2)/2; i >= 0; --i)                {                        _AdjustDown(i);                }            Disp(_a, size);        }        //Pop时，先将第一个与最后一个交换，（这样不至于打乱其他子堆的顺序），然后        //删除最后一个，再让它下调重新调整顺序        void Pop()               {                size_t _size = _a.size();                assert(_size > 0);                swap(_a[0], _a[_size-1]);                _a.pop_back();                _size = _a.size();                _AdjustDown(0);                Disp(_a, _size);        }        //push一个数据后，让其上调，以调整顺序        void Push(const T& x)        {                _a.push_back(x);                size_t _size = _a.size();                _AdjustUp(_size-1);                Disp(_a, _size);        }        T& Top()        {                assert(!_a.empty());            return _a[0];        }        bool empty()        {                return _a.size() == 0;        }        void Disp(vector a, size_t k)//打印        {                for (size_t j = 0; j < k; j++)                {                        cout << a[j] << " ";                }                cout << endl;        }

在建堆时，首先来定义一个下调函数_AdjustDown（）；用来调整已实现大小堆顺序。

实现思想：

1、找最后一个非叶子结点

2、如果当前结点的孩子结点左孩子大于右孩子，就让child指向最大孩子结点（在此必须满足存在右孩子）

3、如果当前结点小于孩子结点，就交换，下调，将孩子给父亲，孩子结点下移

4、不满足 就break；

   void _AdjustDown(size_t parent)    //     下调        {                size_t child = parent * 2 + 1;                while (child < _a.size())                {                        compare _com;                          if ( child + 1 < _a.size()&&_com(_a[child + 1], _a[child]) )                        {                                ++child;                        }                        if (_com(_a[child],_a[parent]))                        {                                swap(_a[child], _a[parent]);                                parent = child;                                child = parent * 2 + 1;                        }                        else                        {                                break;                        }                }        }

再写一个上调函数_AdjustUp（）当Push一个数时，让它上调，以调整整个堆的顺序。

实现思想：

1、上调，传当前结点，令当前节点为孩子结点，上一结点为父结点，

2、在这里不用考虑左右结点谁大谁小

3、如果孩子结点大于父亲结点，交换，上移

4、不满足 就break；

注意：在此不用考虑左右子数谁大谁小，上调是如果孩子结点比父结点大，那它肯定比兄弟结点大。

void _AdjustUp(size_t child)   //上调        {                compare _com;                size_t parent = (child - 1) / 2;                while (child > 0)                {                        if (_com(_a[child], _a[parent]))                        {                                swap(_a[child], _a[parent]);                                child = parent;                                parent = (child - 1) / 2;                        }                        else                        {                                break;                        }                }        }

三、优先队列

template  class compare = Big>//利用模板的模板参数class PriorityQueue  //优先队列{protected:        Heap _hP;public:        void _push(const T& x)        {                _hP.Push(x);        }        void Pop()        {                _hP.Pop();        }        T& Top()        {                return _hP.Top();        }};测试用例：PriorityQueue s;        s._push(3);        s._push(12);        s._push(5);        s._push(78);        s._push(43);        s._push(10);        s._push(32);    

结果会以大堆形式实现为：

如果将测试用例改为：

PriorityQueue s;        s._push(3);        s._push(12);        s._push(5);        s._push(78);        s._push(43);        s._push(10);        s._push(32);

结果会以小堆实现 为：

感谢你能够认真阅读完这篇文章，希望小编分享的"编程开发中如何实现堆"这篇文章对大家有帮助，同时也希望大家多多支持，关注行业资讯频道，更多相关知识等着你来学习!