【数据结构】堆的实现（包括：默认成员函数，插元素push,删元素pop,访问根节点top，判空，大小）

在数据结构里，堆是一类很重要的结构。堆结构是一组数组对象，咱们能够把它看成是一颗彻底二叉树。ios

最大堆：堆里每个父亲节点大于它的子女节点。编程

最小堆：堆里每个父亲节点小于它的子女节点。数组

如图就是一个最大堆:
数据结构

实现代码时个人测试序列是：int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };ide

咱们把它的图画出来，便于分析。函数

咱们来实现如何将一个数组中的序列转变为最大堆。测试

若咱们知道最大堆的代码后，只需将代码稍微修改一下就能够变成最小堆的代码。或者，咱们能够用仿函数来提升代码的复用性。
spa

实现代码以下：对象

创建头文件heap.hpp
get

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;

#include<assert.h>
#include<vector>

template <class T>
class Heap
{
public:
    Heap()
        :_a(NULL)
    {}


    //构造堆：先把各个元素接收到，再根据堆的特色将元素调整
    Heap(const T* array, size_t size)
    {
        _a.reserve(size);
        for (size_t i = 0; i < size; i++)
        {
            _a.push_back(array[i]);
        }

        //建堆
        int Size = size;
        for (int j = (_a.size() - 2) / 2; j>=0; j --)
        {
            _AdjustDown(j, Size);
        }
    }


    //拷贝构造
    Heap(const vector<T>& vec)
        :_a(NULL)
    {
        _a.reserve(vec.size());
        for (size_t i = 0; i < size; i++)
        {
            _a.push_back(vec[i]);
        }
    }

    //插入一个元素x:先插入到顺序表中，再根据具体元素大小向上调整肯定插入元素的位置
    void Push(const T& x)
    {
        _a.push_back(x);
        _AdjustUp(_a.size() - 1);
    }


    //删除根节点
    void Pop()
    {
        size_t size = _a.size();
        assert(size > 0);//防护式编程，肯定是否能够删除元素
        swap(_a[0], _a[size - 1]);//若直接删除堆的根节点，则会使堆结构紊乱
        _a.pop_back();//将根节点与堆的最后一个节点交换位置，此时再对元素删除，以及将其调整于合适位置
        size = _a.size();
        _AdjustDown(0,size);
    }


    //访问堆的根节点
    T& GetTop()
    {
        size_t size = _a.size();
        assert(size > 0);
        return _a[0];
    }


    //将根节点向下调整
    void _AdjustDown(size_t parent,size_t size)
    {
        size_t child = 2 * parent + 1;
        while (child<size)
        {
            if (child+1 < size && _a[child] < _a[child + 1])
            {
                child++;
            }
            if (_a[child] > _a[parent])
            {
                swap(_a[child], _a[parent]);
                parent = child;
                child = 2 * parent + 1;
            }
            else
            {
                break;
            }
        }        
    }


    //向上调整
    void _AdjustUp(int child)
    {
        //不管插节点后为左子树仍是右子树，均可用(child-2)/2计算出此时父节点的下标
        int parent = (child - 1) / 2;
        int size = _a.size();//size用int，若用size_t循环条件且为>=0则死循环
        while (child>0)//当child=0,说明此时已经到根节点位置，无需继续上调
        {
            //向上调整时，无需看左右节点哪一个值大，只须要看是否父节点<根节点
            if (_a[child]>_a[parent])
            {
                swap(_a[child], _a[parent]);
                child = parent;
                parent = (child-1)/2;
            }
            else
            {
                break;
            }
        }
    }


    bool Empty()
    {
        size_t size = _a.size();
        assert(size >= 0);
        return size == 0;
    }


    size_t Size()
    {
        size_t size = _a.size();
        assert(size >= 0);
        return size;
    }
    
    
    void PrintHeap()
    {
        cout << "堆的序列为：" << endl;
        for (int i = 0; i < Size(); i++)
        {
            cout << _a[i] << "  ";
        }
        cout << endl;
    }
private:
    vector<T> _a;
};

创建源文件heap.cpp

#define _CRT_SECURE_NO_WARNINGS 1

#include "heap.hpp"

void Test()
{
    int a[] = { 10, 11, 13, 12, 16, 18, 15, 17, 14, 19 };
    Heap<int> h1(a, sizeof(a) / sizeof(a[0]));
    Heap<int> h2(h1);
    cout<<h1.GetTop()<<endl;
    cout << h1.Size() << endl;

    h1.Push(20);
    cout << h1.GetTop() << endl;

    h1.Pop();
    cout << h1.Size() << endl;

}


int main()
{
    Test();
    system("pause");
    return 0;
}

关于size(),GetTop()等函数咱们能够经过测试函数Test()写出适当的测试用例来测试。