阅览、认为、编写代码！
/*********************************************
* 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;
}
測试结果：
watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvaHVzdHlhbmdqdQ==/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="">
版权声明：本文博主原创文章。博客，未经同意，不得转载。