堆的简单实现

堆是一种重要的数据结构，在很多地方都有使用，这里用c++模拟实现堆算法

1.首先，堆在底层的数据是用数组进行存储的

2.用stl提供的vector进行数据的管理

3.建队使用需要使用向上调整算法

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

4.插入数据时需要在尾部插入，然后进行_AdjustDown()

5.删除是需要删掉根节点

基本接口就实现这几个，在堆的应用之中最常用的也是这几个接口，下面是全部代码

#pragma once
#include <vector>
#include<iostream>
using namespace std;
template <class T>
class Heap
{
public:
    Heap()//无参构造函数
    {}
    Heap(const T* a,size_t n)//使用数组初始化堆 
    {
        size_t i = 0;
        _a.reserve(n);
        for (i = 0; i < n; i++)
        {
            _a.push_back(a[i]);
        }
        int parent = (n - 2) / 2;
        for (; parent >= 0; parent--)
        {
            _AdjustDown(parent);
        }
    }

    void Push(const T& x)//插入
    {
        _a.push_back(x);
        _AdjustUp(_a.size()-1);
    }

    void Pop()//删除
    {
        if (!_a.empty())
        {
            size_t n = _a.size();
            swap(_a[0], _a[n - 1]);
            _a.pop_back();
            _AdjustDown(0);
        }
    }

    bool Find(const T& x)//查找
    {
        if (!_a.empty())
        {
            size_t n = _a.size();
            for (size_t i = 0; i < n; i++)
            {
                if (_a[i] == x)
                    return true;
            }
        }
        return false;
    }

    void Disp(size_t n)//打印  
    {
        for (size_t i = 0; i < n; i++)
        {
            cout << _a[i] << " ";
        }
        cout << endl;
    }

protected:
    void _AdjustDown(size_t root)//向上调整
    {
        size_t parent = root;
        size_t child = parent * 2 + 1;
        while (child < _a.size())
        {
            if ((child + 1 < _a.size()) && (_a[child] < _a[child + 1]))
            ++child;
            if (_a[parent] < _a[child])
            {
                swap(_a[child], _a[parent]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }

    void _AdjustUp(int child)//向下调整
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            if (_a[child] > _a[parent])
            {
                swap(_a[child], _a[parent]);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }
    }
protected:
    vector<int> _a;
};

void TestHeap()
{
    int a[] = { 16, 15, 18, 13, 25, 27, 9, 42 };
    Heap<int> heap(a, sizeof(a) / sizeof(a[0]));
    heap.Push(23);
    heap.Pop();
    heap.Disp(sizeof(a) / sizeof(a[0]));
    cout << heap.Find(9) << endl;
}