2013-07-23 22:37:12

 

注意几点：

1. 堆的性质虽然借助树的概念来定义的，但实际实现用数组即可，数组的下标可表征父节点与左右子树的关系；
2. 数组下标从1开始时，下标为i的结点的左子树的下标为 2i，右子树下标为2i + 1;数组下标从0开始时，下标为i的结点的左子树的下标为 2i + 1，右子树下标为2i + 2;
3. 注意循环结束条件；
4. 下面的代码中输入数组是利用随机数产生函数rand()得到的，用srand()函数，可给rand()提供seed，这样每次运行时就会得到不同的随机数序列；但要注意其使用方法

 

代码：

1 #include 
     
        2 #include 
      
         3 #include 
       
          4 using namespace std;  5   6 typedef int DataType;  7 const int MaxSize = 100000000;  8   9 //显示数组元素，lengthOfArray为数组中元素个数 10 void DisplayArray(const DataType arrayToDiaplay[],const size_t lengthOfArray) 11 { 12     assert(NULL != arrayToDiaplay); 13  14     for (size_t index = 0;index < lengthOfArray;++index) 15     { 16         cout<
        
         <<"\t"; 17     } 18  19     cout<
         
           lengthOfHeapArray) ? false : true; 28  } 29  30  //判断在最大下标为lengthOfHeapArray（为数组中元素个数-1）的数组中，下标为positionToAdjust的元素是否有右子树 31  bool IsHasRightChild(const size_t lengthOfHeapArray,const size_t positionToAdjust) 32  { 33      size_t indexOfRightChild = 2 * positionToAdjust + 2; 34  35      return (indexOfRightChild > lengthOfHeapArray) ? false : true; 36  } 37  38   //数组下标以1开始时，下标为i的结点的左子树下标为2i,左子树下标为2i+1 39  //数组下标以0开始时，下标为i的结点的左子树下标为2i+1,左子树下标为2i+2 40  //调用函数要保证positionToAdjust是小于 41  void HeapAdjust(DataType heapArray[],const size_t lengthOfHeapArray,const size_t positionToAdjust) 42  { 43     DataType leftChildIndex = 2 * positionToAdjust + 1; 44     DataType rightChildIndex = 2 * positionToAdjust + 2; 45  46     size_t positionOfMax = positionToAdjust;   //只用positionOfMax记录最大数的下标即可 47  48     if ( !IsHasLeftChild(lengthOfHeapArray,positionToAdjust)     //若为叶节点，直接返回 49         && !IsHasRightChild(lengthOfHeapArray,positionToAdjust) ) 50     { 51         return; 52     } 53           54     if ( IsHasLeftChild(lengthOfHeapArray,positionToAdjust)    55         && heapArray[leftChildIndex] > heapArray[positionOfMax]) 56     { 57         //max = heapArray[leftChildIndex]; 58         positionOfMax = leftChildIndex; 59     } 60  61     if ( IsHasRightChild(lengthOfHeapArray,positionToAdjust)  62         && heapArray[rightChildIndex] > heapArray[positionOfMax]) 63     { 64         //max = heapArray[rightChildIndex]; 65         positionOfMax = rightChildIndex; 66     } 67  68     if ( positionOfMax == positionToAdjust )    //结点大于左子树与右子树，不需调整 69     { 70         return; 71     } 72     else 73     { 74         //swap(heapArray[positionToAdjust],max); 75         swap(heapArray[positionToAdjust],heapArray[positionOfMax]); 76         HeapAdjust(heapArray,lengthOfHeapArray,positionOfMax); 77     } 78  } 79  80  //堆排序,lengthOfHeapArray为数组的最大下标为（为数组中元素个数-1） 81  void HeapSort(DataType heapArray[],const size_t lengthOfHeapArray) 82  { 83     assert(NULL != heapArray); 84     //size_t index;  //使用size_t类型，下面的for循环不能结束0 - 1 = 2^32 - 1 85     int index; 86      87     for (index = (lengthOfHeapArray - 1)/2;index >= 0;--index) 88     { 89         HeapAdjust(heapArray,lengthOfHeapArray,index); 90     } 91  92     for (index = lengthOfHeapArray;index > 0;--index) 93     { 94         swap(heapArray[0],heapArray[index]); 95         HeapAdjust(heapArray,index - 1,0);  //不是HeapAdjust(heapArray,lengthOfHeapArray,0); 96     } 97  } 98  99  //产生在[lowBound,upperBound - 1]区间的随机数100  int RandomIntGenerate(int lowBound, int upperBound)101  {    102      return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + 1) );103  }104 105  //测试“脚手架”106 void TestDriver()107 {    108     DataType *unsortedArray = new int[MaxSize];109     size_t lengthOfUnsortedArray = 0;110     int MinRandomInt;111     int MaxRandomInt;112     size_t i;113     int timeStart = 0;114     double timeCostAverage = 0;115 116     DataType *heapArray = unsortedArray;117     //size_t lengthOfHeapArray = lengthOfUnsortedArray;  //若lengthOfUnsortedArray未初始化，不能将其赋给其他变量，否则报错118     size_t *lengthOfHeapArray = &lengthOfUnsortedArray;119 120     cout<<"please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :"<
          
           >lengthOfUnsortedArray>>MinRandomInt>>MaxRandomInt;122 123 srand((unsigned) time(NULL)); //随机数产生的seed124 for (i = 0;i < lengthOfUnsortedArray;++i) //准备待排序数组125 {126 //srand((unsigned) time(NULL)); //随机数产生的seed,不能放在循环体内，否则unsortedArray将会是全部相同的数127 unsortedArray[i] = RandomIntGenerate(MinRandomInt,MaxRandomInt);128 }129 130 /*cout<<"the unsorted array is :"<
           
            < lengthOfUnsortedArray - 1;++i) //检查排序是否正确140 {141 if (unsortedArray[i] > unsortedArray[i + 1])142 {143 cout<<"sort bug i = "<
            <
           
          
         
        
       
      
     

输入10个元素时，运行结果为：

please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :10 0 100the unsorted array is :20      34      24      36      5       43      6       92      75      82the average time cost per data is : 0 nsthe sorted array is :5       6       20      24      34      36      43      75      82      92请按任意键继续. . .

可通过增加输入个数，测试时间性能，此处不再给出，后面在与其他算法进行比较。