《算法導論》中典型的最大堆排序

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;

template<class T> void Max_Heap(T a[],int i,int size)
{
    int r = 2*i + 2;
    int l = 2*i + 1;
    int largest;
    if (l<size && a[l]>=a[i])
    {
        largest = l;
    }
    else
        largest = i;
    if (r<size && a[r] >=a[largest])
    {
        largest = r;
    }
    if (largest != i)
    {
        swap(a[largest],a[i]);
        Max_Heap(a,largest,size);
    }
}

template<class T> void Build_Max_Heap(T a[],int size)
{
    for (int i=size/2;i>=0;i--)
    {
        Max_Heap(a,i,size);
    }
}

template<class T> void HeapSort(T a[],int size)
{
    Build_Max_Heap(a,size);
    for (int i=size-1;i>=1;i--)
    {
        swap(a[i],a[0]);       //將最大數換到數組末尾
        //show(a,size);
        size--;
        Max_Heap(a,0,size);
    }
}

template<class T> void show(T a[],int size)
{
    cout<<"排序后結果為"<<endl;
    for (int i=0;i<size;i++)
    {
        cout<<a[i]<<endl;
    }
}

int main()
{
    int num;
    cin>>num;
    char* input = new char[num];
    for (int i=0;i<num;i++)
    {
        cin>>input[i];
    }

//    Build_Max_Heap(input,num);     //建立最大堆
    HeapSort(input,num);           //堆排序
    show(input,num);
}