《github一天一道算法题》：堆算法接口实现（堆排序、堆插入和堆取最值并删除）

看书、思考、写代码！

/*********************************************
 * copyright@hustyangju
 * blog: http://blog.csdn.net/hustyangju
 * 题目：堆排序实现，另外实现接口：取堆最大值并删除、堆插入
 * 思路：堆是在顺序数组原址上实现的，利用完全二叉树的性质，更具最大堆和最小堆的定义实现的。
 * 经典应用场景：内存中堆数据管理
 * 空间复杂度：堆排序是在原址上实现的，为0
 * 时间复杂度：堆排序为O(n lgn) ，取最值O（1），插入最坏为O(lgn)
*********************************************/
#include <iostream>
#include <algorithm>

using namespace::std;

//对堆排序实现类的定义
class HeapSort
{
 public:
     HeapSort(int *pArray , int nArraySize);//constructor
     ~HeapSort();//destructor
 private:
    int *m_pA;//points to an array
    int m_nHeapSize;//stands for the size
 public:
    void BuildMaxHeap(); //build a heap
    void Sort();//建一个最大堆并排序，按照顺序（由小到大）放在原数组
    int  PopMaxHeap();//取最大堆的最大值
    void InsertMaxHeap(int a);//插入一个新值到最大堆，其实就是在元素尾部加入一个值，再维护最大堆的性质
    void print();//顺序输出数组
 protected:
    int LeftChild(int node);//取左孩子下标
    int RightChild(int node);//取右孩子下标
    int Parent(int node);//取父节点下标
    void MaxHeapify(int nIndex);//justify the heap
 };

//构造函数初始化
HeapSort::HeapSort( int *pArray, int nArraySize )
{
     m_pA = pArray;
     m_nHeapSize = nArraySize;
}

//析构函数
HeapSort::~HeapSort()
{
}

//取左孩子下标，注意沿袭数组从0开始的习惯
int HeapSort::LeftChild(int node)
{
   return 2*node + 1;// the array starts from 0
}

//取右孩子下标
int HeapSort::RightChild(int node)
{
     return 2*node + 2;
}

//取父节点下标
int HeapSort::Parent(int node)
{
   return (node-1)/2 ;
}

//利用递归维护最大堆的性质，前提是已经建好最大堆，只对变动的结点调用该函数
void HeapSort::MaxHeapify(int nIndex)
{
     int nLeft = LeftChild(nIndex);
     int nRight = RightChild(nIndex);

     int nLargest = nIndex;

     if( (nLeft < m_nHeapSize) && (m_pA[nLeft] > m_pA[nIndex]) )
         nLargest = nLeft;

     if( (nRight < m_nHeapSize) && (m_pA[nRight] > m_pA[nLargest]) )
        nLargest = nRight;

     if ( nLargest != nIndex )//如果有结点变动才继续递归
    {
         swap<int>(m_pA[nIndex], m_pA[nLargest]);
         MaxHeapify(nLargest);
     }
 }

//建造最大堆，思路：对于一个完全二叉树，子数组A[int((n-1)/2)+1]~A[n-1]为叶子结点
//A[0]~A[int((n-1)/2)]为非叶子结点，从下到上，从最后一个非叶子结点开始维护最大堆的性质
 void HeapSort::BuildMaxHeap()
 {
     if( m_pA == NULL )
         return;

     for( int i = (m_nHeapSize - 1)/2; i >= 0; i-- )
    {
         MaxHeapify(i);
     }
}

 //不断取最大堆的最大值A[0]与最后一个元素交换，将最大值放在数组后面，顺序排列数组
 void HeapSort::Sort()
{
     if( m_pA == NULL )
         return;
     if( m_nHeapSize == 0 )
        return;
    for( int i = m_nHeapSize - 1; i > 0; i-- )
     {
        swap<int>(m_pA[i], m_pA[0]);
         m_nHeapSize -= 1;//这个表达式具有破坏性！！！
         MaxHeapify(0);
    }
}

 //取出最大值，并在堆中删除
 int HeapSort::PopMaxHeap()
 {
    /*if( m_pA == NULL )
          return ;
      if( m_nHeapSize == 0 )
         return ;*/
    int a= m_pA[0];
    m_pA[0]=m_pA[m_nHeapSize-1];
    m_nHeapSize -= 1;
       MaxHeapify(0);
    return a;
 }

 //插入一个值，思路：放在数组最后面（符合数组插入常识），再逐层回溯维护最大堆的性质
 void HeapSort::InsertMaxHeap(int a)
 {
 /*
    if( m_pA == NULL )
          return;
      if( m_nHeapSize == 0 )
         return;
         */
    m_nHeapSize += 1;
    m_pA[m_nHeapSize-1]=a;
    int index=m_nHeapSize-1;
    while(index>0)
    {
        if(m_pA[index]>m_pA[Parent(index)])
        {
            swap(m_pA[index], m_pA[Parent(index)]);
            index=Parent(index);
        }
        else
            index=0;//注意这里，某一层已经满足最大堆的性质了，就不需要再回溯了
    }
 }

 //顺序输出数组
 void HeapSort::print()
 {
     for(int i=0;i<m_nHeapSize;i++)
         cout<<m_pA[i]<<" ";
     cout<<endl;
 }
 int main()
 {
    int a[10]={6,5,9,8,1,0,3,2,7,4};
    //int max;
    cout<<"input an array::"<<endl;
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
    HeapSort myHeap(a,10);
    myHeap.BuildMaxHeap();
    cout<<"pop the max number:"<<endl;
    cout<<"the max="<<myHeap.PopMaxHeap()<<endl;
    cout<<"after pop:"<<endl;
    myHeap.print();
    myHeap.InsertMaxHeap(11);
    cout<<"insert a number and sort:"<<endl;
    myHeap.Sort();
   // myHeap.print();
    for(int i=0;i<10;i++)
        cout<<a[i]<<" ";
    cout<<endl;
 }