#include <iostream>
#include <bits/stdc++.h>
using namespace std;

template<typename T>
class maxHeap
{
private:
    T* data;  //保存元素的数组指针
    int sz;  //最大堆里的元素个数
    int cap;  //容量

    void shiftup(int k);   //将第k个元素向上调整
    void shiftdown(int k);  //将第k个元素向下调整


public:
    maxHeap(int n);  //构造函数
    maxHeap(const maxHeap& mh);  //拷贝构造函数


    maxHeap& operator=(const maxHeap& mh) ; //赋值构造函数


    maxHeap(T arr[],int n);  //从数组调整成堆


    int heapsize()const;

    int heapcap()const;

    bool heap_insert(T num);

    void print();

    T extractmax();
};

template<typename T>
void maxHeap<T>::shiftup(int k)  //将第k个元素向上调整
{
    while((k-1)/2>=0)  //还有父亲节点
    {
        if(data[k]<=data[(k-1)/2])  //已经到适合的位置
        {
            break;
        }
        else
        {
            swap(data[k],data[(k-1)/2]); //和父节点进行交换
            k=(k-1)/2;    //对新的父节点重复相同的操作
        }
    }
}

template<typename T>
maxHeap<T>::maxHeap(int n) //构造函数
{
    data=new T[n];  //开辟一个大小为n的数组空间
    sz=0;
    cap=n;
}

template<typename T>
maxHeap<T>::maxHeap(const maxHeap& mh)  //拷贝构造函数
{
    sz=mh.heapsize();
    cap=mh.heapcap();

    if(sz==0)
    {
        return;
    }
    data=new T[sz];
    for(int i=0; i<sz; i++)
    {
        data[i]=mh.data[i];
    }
}

template<typename T>
maxHeap<T>& maxHeap<T>:: operator=(const maxHeap& mh)  //赋值构造函数
{
    if(*this=mh)
    {
        return *this;
    }
    //释放原来的空间，重新分配空间进行存储
    delete[] data;
    sz=mh.heapsize();
    cap=mh.heapcap();
    if(cap==0)
    {
        return *this;
    }
    data=new T[cap];
    for(int i=0; i<sz; i++)
    {
        data[i]=mh.data[i];
    }
    return *this;
}

template<typename T>
maxHeap<T>::maxHeap(T arr[],int n)  //从数组调整成堆
{
    sz=n;
    cap=n;
    data=new T[n];
    for(int i=0; i<n; i++)
    {
        data[i]=arr[i];
    }
    for(int i=(n-2)/2; i>=0; i--)  //第一个非叶子节点为(n-2)/2
    {
        shiftdown(i);
    }
}

template<typename T>
int maxHeap<T>::heapsize()const
{
    return sz;
}
template<typename T>
int maxHeap<T>::heapcap()const
{
    return cap;
}
template<typename T>
bool maxHeap<T>::heap_insert(T num)
{
    if(sz>=cap)
    {
        return false;
    }
    data[sz]=num;
    sz++;
    shiftup(sz-1);
    return true;
}
template<typename T>
void maxHeap<T>:: print()
{
    for(int i=0; i<sz; i++)
    {
        cout<<data[i]<<" ";
    }
    cout<<endl;

}
template<typename T>
T maxHeap<T>:: extractmax()
{
    T temp=data[0];
    data[0]=data[sz-1];
    sz--;
    shiftdown(0);
    return temp;
}


template<typename T>
void maxHeap<T>::shiftdown(int k)  //将第k个元素向下调整
{
    while(2*k+1<sz)  //该节点有左孩子
    {
        int j=2*k+1;
        if(j+1<sz && data[j]<data[j+1])
        {
            j=j+1;
        }
        if(data[k]>=data[j])
        {
            break;
        }
        swap(data[k],data[j]);
        k=j;
    }
}

template<typename T>
void heapsort(T arr[],int n)   //将每个元素依次插入一个空堆中,算法复杂度为O(nlogn)
{
    maxHeap<T> mh=maxHeap<T>(n);
    for(int i=0; i<n; i++)
    {
        mh.heap_insert(arr[i]);
    }
    mh.print();
}

template<typename T>
void heapsort2(T arr[],int n)  //将一个数组调整成堆,算法复杂度为O(n)
{
    maxHeap<T> mh=maxHeap<T>(arr,n);
    mh.print();
}

int main()
{
    maxHeap<int> mp(100);
    srand(time(NULL));
    for(int i=0; i<15; i++)
    {
        mp.heap_insert(rand()%100);
    }
    mp.print();
    cout<<mp.extractmax()<<endl;
    mp.print();
    int a[15];
    for(int i=0;i<15;i++)
    {
        a[i]=rand()%100;
    }
    heapsort2<int>(a,15);


    return 0;
}

原地堆排序：

void __shiftDown(int arr[],int n,int k)
{
    while(2*k+1<n)
    {
        int j=2*k+1;
        if(j+1<n && arr[j]<arr[j+1])
        {
            j++;
        }
        if(arr[k]>=arr[j])
            break;
        swap(arr[k],arr[j]);
        k=j;
    }
    return;
}

void heapSort(int arr[],int n)
{
    //heapify
    for(int i=(n-2)/2; i>=0; i--)
    {
        __shiftDown(arr,n,i);
    }
    for(int i=n-1;i>0;i--)
    {
        swap(arr[0],arr[i]);
        __shiftDown(arr,i,0);
    }
    return;
}

如有哪里不对，欢迎批评指正！