//// main.cpp// Heap//// Created by xin wang on 5/5/15.// Copyright (c) 2015 xin wang. All rights reserved.//#include <iostream>class OutOfBound{public:OutOfBound(){std::cout<<"越界"<<std::endl;}};class NoMen{public:NoMen(){std::cout<<"No Men"<<std::endl;}};template <class T>class MaxHeap{public:MaxHeap(int MaxHeapSize=10);~MaxHeap(){delete []heap;}int Size()const{return CurrentSize;}T Max(){if (CurrentSize==0) {throw OutOfBound();}return heap[1];}MaxHeap<T>& Insert(const T& x);MaxHeap<T>& DeleteMax(T& x);void Initialize(T a[],int size,int ArraySize);void Deactivate(){heap=0;}private:int CurrentSize;int MaxSize;T *heap;};template <class T>MaxHeap<T>::MaxHeap(int MaxHeapSize){MaxSize = MaxHeapSize;heap = new T[MaxSize+1];CurrentSize=0;}//最大堆的插入template <class T>MaxHeap<T>& MaxHeap<T>::Insert(const T& x){//把x插入到最大堆中if (CurrentSize==MaxSize) {throw NoMen();//没有足够的空间}int i= ++CurrentSize;while (i != 1&& x>heap[i/2]) {heap[i] = heap[i/2];//将元素下移i/=2;//移向父节点}heap[i]=x;return *this;}//最大堆的删除template <class T>MaxHeap<T>& MaxHeap<T>::DeleteMax(T& x){//将最大元素放入x，并从堆中删除最大元素if (CurrentSize==0) {//越界throw OutOfBound();}x=heap[1];//将最大的元素放入xT y = heap[CurrentSize–];int i=1,ci=2;while (ci<=CurrentSize) {if (ci<CurrentSize && heap[ci]<heap[ci+1]) {ci++;//找到较大的孩子的位置}if (y>heap[ci]) {//能把y放入heap[i]break;}heap[i]=heap[ci];//将孩子上移i=ci;//下移一层ci*=2;}heap[i]=y;return *this;}template <class T>void MaxHeap<T>::Initialize(T a[], int size, int ArraySize){delete []heap;heap=a;CurrentSize = size;MaxSize = ArraySize;for (int i= CurrentSize/2; i>=1; i–) {T y = heap[i];//子树的根int c = 2*i;while (c<=CurrentSize) {if (c <CurrentSize && heap[c]<heap[c+1]){c++;}if (y>=heap[c]) {break;}heap[c/2]=heap[c];//将孩子上移c*=2;//下移一层}heap[c/2]=y;}}template <class T>void HeapSort(T a[],int n){//对a［1:n］进行排序MaxHeap<T> H(1);H.Initialize(a,n,n);// for (int ii=1; ii<=n; ii++) {//std::cout<<a[ii]<<" ";// }T x;std::cout<<"output:"<<std::endl;for (int i=n-1; i>=1; i–) {H.DeleteMax(x);std::cout<<x<<" ";a[i+1] =x;}H.Deactivate();//析构}int main(int argc, const char * argv[]) {// insert code here…,int array[20];std::cout<<"please enter an array,0 is end"<<std::endl;int i=0;int b=1;//初始化数组，，输入0结束while(std::cin>>i){if (i==0) {break;}array[b]=i;b++;}HeapSort(array, b);return 0;}
因为有梦，所以勇敢出发，选择出发，便只顾风雨兼程。
