一、什么是堆(Heap)

可以看作是一个数组表示的完全二叉树。
堆总是满足下列性质：

1) 堆中某个节点的值总是不大于或不小于其父节点的值。
2) 堆总是一棵完全二叉树。

将根节点最大的堆叫做最大堆(MaxHeap)。
根节点最小的堆叫做最小堆(MinHeap)。

二、堆的抽象数据类型描述

操作集: $最大堆H \in MaxHeap,元素item \in ElementType$ 。
主要操作有:

操作	说明
MaxHeap Create(int MaxSize)	创建一个空的最大堆。
Boolean IsFull(MaxHeap H)	判断最大堆H是否已满。
Insert(MaxHeap H,ElementType item)	将元素item插入最大堆H。
Boolean IsEmpty(MaxHeap H)	判断最大堆H是否为空。
ElementType DeleteMax(MaxHeap H)	返回H中最大元素。

三、堆的实现

#ifndef MAXHEAP
#define MAXHEAP
#include<vector>
using namespace std;

template<class T>
class MyMaxHeap
{
public:
    MyMaxHeap(T data[], int len);   //构造函数
    MyMaxHeap(int capacity);        //构造一个空堆
    ~MyMaxHeap(){};                 //析构函数
    bool IsFull();                  //判断最大堆H是否已满。
    void Insert(T item);        //将元素item插入最大堆H。
    bool IsEmpty();                 //判断最大堆H是否为空
    T DeleteMax();          //返回最大元素

private:
    vector<T>_vecdata;
    int _size;                      //元素数量
    int _capacity;                  //堆的大小
    void _swap(int i, int j );      //元素交换
    void _sink(int index);          //元素下沉
    void _floating(int index);      //元素上浮
};

#endif

#include <iostream>
#include "heap.h"
using namespace std;
//构造函数
template <class T>
MyMaxHeap<T>::MyMaxHeap(T data[], int len) :_size(0), _capacity(len)
{
    _vecdata.resize(_capacity);
    for (int i = 0; i < len; i++)
    {
        if (IsFull())
        {
            cout << "MaxHeap is full!" << endl;
        }
        else
        {
            _vecdata[_size] = data[i];
            ++_size;
            _floating(_size);
        }
    }
}

template <class T>
//构造一个空堆
MyMaxHeap<T>::MyMaxHeap(int capacity) :_size(0), _capacity(capacity)
{
    _vecdata.resize(_capacity);
}

template <class T>
//判断最大堆H是否已满
bool MyMaxHeap<T>::IsFull()
{
    if (_capacity == _size)
        return true;
    return false;
}

template <class T>
//将元素item插入最大堆H
void MyMaxHeap<T>::Insert(T item)
{
    if (IsFull())
    {
        cout << "the MaxHeap is full!!" << endl;
        return;
    }
   
    _vecdata[_size] = item;
    ++_size;
    _floating(_size);
}

template <class T>
//判断最大堆H是否为空
bool MyMaxHeap<T>::IsEmpty()
{
    return _size == 0;
}

template <class T>
//返回最大元素
T MyMaxHeap<T>::DeleteMax()
{
    if (IsEmpty())
    {
        cout << "the MaxHeap is empty!" << endl;
        return nullptr;
    };
    T max_data = _vecdata[0];
    _vecdata[0] = _vecdata[_size - 1];
    --_size;
    _sink(_size + 1);
    return max_data;
}

template <class T>
//元素交换
void MyMaxHeap<T>::_swap(int i, int j)
{
    T temp = _vecdata[i];
    _vecdata[i] = _vecdata[j];
    _vecdata[j] = temp;
    return;
}

template <class T>
//元素下沉
void MyMaxHeap<T>::_sink(int index)
{
    int i = index;
    while (i * 2 <= _size)
    {
        //对比左节点
        if (_vecdata[i - 1] < _vecdata[i * 2 - 1])
        {
            _swap(i - 1, i * 2 - 1);
            if (i * 2 + 1 <= _size && _vecdata[i - 1] < _vecdata[i * 2])
                _swap(i - 1, i * 2);
            i = i * 2;
        }
        //对比右节点
        else if (i * 2 + 1 <= _size && _vecdata[i - 1] < _vecdata[i * 2])
        {
            _swap(i - 1, i * 2);
            i = i * 2 + 1;
        }
        else
            break;
    }
}

template <class T>
//元素上浮
void MyMaxHeap<T>::_floating(int index)
{
    if (_size == 1)
        return;
    for (int i = index; i > 0; i *= 0.5)
    {
        if (_vecdata[i - 1] > _vecdata[i * 0.5 - 1])
            _swap(i - 1, i * 0.5 - 1);
        else
            break;
    }
}