用模板实现堆

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

堆结构的二叉树存储是

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

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

这是一个普通的堆，我们想把它变成最大堆，就必须了解最大堆的特点。然后我们对它进行调整，保证每个父节点的都大于孩子节点。

我们先调整这个二叉树的一部分，从它的最后一个节点开始调整，图中红色箭头开始调整，如果父节点小于孩子节点，就交换，否则结束。在看下一个节点，一直这样循环，直到全部调整完。

代码如下：

void _AdjustDown(size_t parent, size_t size)        {                size_t child = 2 * parent + 1;                while (child < size)                {                        //child + 1 < size保证是最后一个节点                        if (child + 1 < size&&_arr[child] < _arr[child + 1])                        {                                child++;//孩子节点最大的一个节点                        }                        //交换                        if (_arr[child]>_arr[parent])                        {                                swap(_arr[child],_arr[parent]);                                parent = child;                                child = 2 * parent + 1;                        }                        else                        {                                break;                        }                }        }

如果想把它调整成最小堆，必须符合每个父节点的都小于孩子节点，代码原理和最大堆相似。

代码如下：

void _AdjustUp(int child)        {                int parent = (child - 1) / 2;                int size = _arr.size();                while (child > 0)                {                        if (_arr[child] > _arr[parent])                        {                                swap(_arr[child], _arr[parent]);                                child = parent;                                parent = (child - 1) / 2;                        }                        else                        {                                break;                        }                }        }

下面我给出完整代码，构造函数用的是调整成大堆。为了让代码更简洁，实现过程借用了库函数中的vector。

代码如下：

Heap.h中

#include#include template class Heap{public:        Heap()                :_arr(NULL)        {}        //构造函数        Heap(const T*arr, size_t size)        {                _arr.reserve(size);                for (size_t i = 0; i < size; i++)                {                        _arr.push_back(arr[i]);                }                for (int j = (_arr.size() - 2) / 2; j >= 0; j--)                {                        _AdjustDown(j, size);                }        }        //拷贝构造        Heap(const vector& h)        {                _arr.reserve(_arr.size());                for (size_t i = 0; i < _arr.size(); i++)                {                        _arr.push_back(h[i]);                }        }        //先储存在顺序表中，在进行下调        void push(const T& x)        {                _arr.push_back(x);                _AdjustUp(_arr.size()-1);        }        //删除        void pop()        {                size_t size = _arr.size();                assert(size > 0);                swap(_arr[0], _arr[size - 1]);//先把根结点和要删除的结点交换                _arr.pop_back();//然后删除                size = _arr.size();                _AdjustDown(0, size);//最后上调        }        //堆是否为空        bool Empty()        {                size_t size = _arr.size();                assert(size >= 0);                return size == 0;        }        //堆的大小        size_t Size()        {                size_t size = _arr.size();                assert(size >= 0);                return size;        }        //访问根结点        T& Top()        {                size_t size = _arr.size();                assert(size > 0);                return _arr[0];        }        void Print()        {                for (int i = 0; i < Size(); i++)                {                        cout << _arr[i] << " ";                }                cout << endl;        }protected:        //下调        void _AdjustDown(size_t parent, size_t size)        {                size_t child = 2 * parent + 1;                while (child < size)                {                        //child + 1 < size保证是最后一个节点                        if (child + 1 < size&&_arr[child] < _arr[child + 1])                        {                                child++;//孩子节点最大的一个节点                        }                        //交换                        if (_arr[child]>_arr[parent])                        {                                swap(_arr[child],_arr[parent]);                                parent = child;                                child = 2 * parent + 1;                        }                        else                        {                                break;                        }                }        }        //上调        void _AdjustUp(int child)        {                int parent = (child - 1) / 2;                int size = _arr.size();                while (child > 0)                {                        if (_arr[child] > _arr[parent])                        {                                swap(_arr[child], _arr[parent]);                                child = parent;                                parent = (child - 1) / 2;                        }                        else                        {                                break;                        }                }        }protected:        vector _arr;};

test.cpp中

#includeusing namespace std;#include"Heap.h"void Test(){        int a[] = { 10, 16, 18, 12, 11, 13, 15, 17, 14, 19 };        Heap h(a, sizeof(a) / sizeof(a[0]));        h.Print();        h.push(20);        h.Print();        h.pop();        h.Print();        Heap h2(h);        h2.Print();}int main(){        Test();        system("pause");        return 0;}