堆Heap（最小堆）

#pragma once
#include <vector>

template<class T>
class Heap
{
public:
            Heap()
            {}
            Heap(const int *a,size_t size)
            {
                        for(int i = 0;i < size;++i)
                        {
                                    _array.push_back(a[i]);
                        }
                        int root = (_array.size() - 2)/2;//找第一个非叶子结点
                        while (root>=0)
                        {
                                    AdjustDown(root--);
                        }
            }
            bool IsEmpty()const
            {
                        return _array.size() == 0;
            }
            T& top()
            {
                        if(_array.size() != 0)
                          return _array[0];
            }
            void pop()
            {
                        if(_array.size() == 0)
                        {
                                    return;
                        }
                        swap(_array[0],_array[_array.size() - 1]);
                        _array.pop_back();
                        if(_array.size() > 1)
                                      AdjustDown(0);
            }
            void push(const T& x)
            {
                        _array.push_back(x);
                        if(_array.size() > 1)
                             AdjustUp(_array.size() - 1);
            }
protected:
    void AdjustUp(int child)
            {
                        while (child >= 1)
                        {
                                    int root = (child - 1) / 2;
                                    if (_array[root] > _array[child])
                                    {
                                                swap(_array[root], _array[child]);
                                    }
                                    child = root;
                        }
            }
            void AdjustDown(int root)
            {
                        while(root <= (_array.size() - 2) / 2)
                        {
                                    int child;
                                    if(root*2 + 2 < _array.size())
                                    {
                                                child = _array[root*2 +1] > _array[root*2 + 2]?root*2 +2:root*2 +1;
                                    }
                                    else
                                    {
                                                child = root*2 +1;
                                    }
                                    if(_array[root] > _array[child])
                                    {
                                                swap(_array[root],_array[child]);
                                    }
                                    root = child;
                        }
            }
protected:
            vector<T> _array;
};

测试：

#include <iostream>
using namespace std;
#include "Heap.h"

void test()
{
    int arr[] = {80,40, 30, 60, 90, 70, 10, 50, 20 };
     Heap<int>hp1(arr,9);
//     cout << "Over!" << endl;

    hp1.push(15);
    while (!hp1.IsEmpty())
    {
        cout << hp1.top()<< " ";
        hp1.pop();
    }
}
int main()
{
    test();
    return 0;

}