前面对选择排序，快速排序，希尔排序，归并排序，冒泡排序都进行了分析，最后一个是堆排序，刚开始实在不想写这个，感觉太麻烦了，无奈搜了一些面经，发现什么百度、腾讯、阿里等，他们都问到了堆排序，所以还是得认真聊一聊堆排序！
堆非常典型的一个应用是优先队列，普通队列是先进先出，优先队列则出队和入队无关，和他们各自的优先级有关！算法可以动态的选择优先级最高的任务执行！而任务的排序使用之前静态的排序方法是做不到的！
还有一个好处是，在N个元素里面选出前M个元素，用前面静态的方法，先排序再提取它的时间复杂度是nlogn,而使用优先队列它可以达到nlogM,把效率提高十几倍。
优先队列正常的思维都是创建一个普通数组，入队时依次添加，出队时遍历一遍谁优先级最高，让它出队。 或者创建一个有序数组，入队的时候维护数组的有序性，这样出队就会按照优先级高低出队。
这两种方法都非常的好，但是都有其局限性，所以发明了第三种方法！（具体什么局限性俺也不知道，先继续往后看吧） 根据图片来看，堆虽然入队效率比普通数组差，出队效率比顺序数组差，但是平均下来效率却是三者中最好的！最差情况普通数组是O（n*n）级别，而堆是O（nlogn）级别。 （二叉堆是一颗）完全二叉树：除了最后一层外，其他层节点个数必须是最大值，并且叶子节点都要从最左边开始依次填满！（只有完全二叉树才能用数组表示）
最大堆：父节点都不小于其子节点。 最小堆：父节点都不大于其子节点。
给这个二叉树从上到下，从左往右标记一下顺序，就会发现，左孩子序号都是父亲序号✖2，右孩子序号都是父亲序号✖2+1.这样的话，入队的值放在最后，怎样保证它能调整到应有最大堆的位置呢？先让他和父节点进行比较，比父节点大就交换，然后依次往上对比，最后交换到自己的位置。
出队怎么出呢？出队就删除现在的根节点，然后把数组最后一个节点交换到根节点的位置，然后对它进行 “下沉”操作，即把它与其较大的那个子节点比大小，如果偏小就和子节点交换。
小插曲：在用Microsoft visiual C++ 进行编译的时候，一直跳出来说 “.exe无法解析的外部符号 _mainCRTStartup”错误。后来发现出错原因是自己建立的文件，其中的main函数并没有被编译，系统根本没有找到你的main函数，可能的原因是在其他地方创建的文件，没有被包含到项目里，解决办法就是右击项目名称，重新创建一个你需要的文件。
下面代码是入队出队的代码，最后以树的形式打印出来，并且保证树是最大堆。树形打印代码是复制粘贴修改后的，不用去记。
#include<iostream> using namespace std;//没有上面头文件std会报错！ #include<ctime> #include<cassert>//等于#include<assert.h> #include <algorithm> #include <string> #include <cmath> template<typename Item> class MaxHeap { private: Item *data;//数组指针 int count;//数组元素个数 int capacity; void shiftup(int k){ //如果该该节点值比父节点大，就把他俩交换一下，注意k>1!! //!注意是while不是if! while(k>1 && data[k/2]<data[k]){ swap(data[k/2],data[k]); k/=2; } } void shiftdown(int k){ //下沉的前提条件是必须要有孩子 while(2*k<=count){ int j=2*k; //先比较两个子节点大小 if(data[j]<data[j+1] && j+1<=count){ j= j+1; } //遇到while循环就要先找到停止条件 if(data[k]>=data[j])//!if里的条件不是<! break; swap(data[k],data[j]); k=j;//!不是k*2! //下面这样写是错误的，如果父节点不小于子节点的情况下， 就不会跳出了，陷入死循环 //if(data[k]<data[j])//!if里的条件不是<! //{ // swap(data[k],data[j]); // k=j;//!不是k*2! //} } //再跟父节点进行比较 } public: //构造函数 MaxHeap(int capacity){ //开辟一个临时数组 data=new Item[capacity+1];//!注意中括号前面的写法! count = 0;//初始化元素个数 this->capacity = capacity; } ~MaxHeap() { delete[] data; } int size()//获取元素个数 { return count; } bool IsEmpty() { return count==0; } void Insert(Item item)//入队插入函数 { assert(count+1<=capacity);//判断要放置的位置有没有越界 data[count+1] = item;//把新元素插入数组中 count++;//元素个数加1 shiftup(count);//把元素上移到对应位置，注意该函数放在私有位置，不对用户开放 } int ExtractMax(){ assert(count>0);//取最大值的时候保证不是第0个 Item ret = data[1]; swap(data[1],data[count]); count--;//取出来之后要记得减去 //对变化后的最大堆下沉之后，又会变成新的最大堆 shiftdown(1); return ret; } public: // 以树状打印整个堆结构 void testPrint(){ // 我们的testPrint只能打印100个元素以内的堆的树状信息 if( size() >= 100 ){ cout<<"This print function can only work for less than 100 int"; return; } // 我们的testPrint只能处理整数信息 if( typeid(Item) != typeid(int) ){ cout <<"This print function can only work for int item"; return; } cout<<"The max heap size is: "<<size()<<endl; cout<<"Data in the max heap: "; for( int i = 1 ; i <= size() ; i ++ ){ // 我们的testPrint要求堆中的所有整数在[0, 100)的范围内 assert( data[i] >= 0 && data[i] < 100 ); cout<<data[i]<<" "; } cout<<endl; cout<<endl; int n = size(); int max_level = 0; int number_per_level = 1; while( n > 0 ) { max_level += 1; n -= number_per_level; number_per_level *= 2; } int max_level_number = int(pow(2.0, max_level-1)); int cur_tree_max_level_number = max_level_number; int index = 1; for( int level = 0 ; level < max_level ; level ++ ){ string line1 = string(max_level_number*3-1, ' '); int cur_level_number = min(count-int(pow(2.0,level))+1,int(pow(2.0,level))); bool isLeft = true; for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){ putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft ); isLeft = !isLeft; } cout<<line1<<endl; if( level == max_level - 1 ) break; string line2 = string(max_level_number*3-1, ' '); for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ ) putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 ); cout<<line2<<endl; cur_tree_max_level_number /= 2; } } private: void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){ int sub_tree_width = (cur_tree_width - 1) / 2; int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width; assert(offset + 1 < (int)line.size()); if( num >= 10 ) { line[offset + 0] = '0' + num / 10; line[offset + 1] = '0' + num % 10; } else{ if( isLeft) line[offset + 0] = '0' + num; else line[offset + 1] = '0' + num; } } void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){ int sub_tree_width = (cur_tree_width - 1) / 2; int sub_sub_tree_width = (sub_tree_width - 1) / 2; int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width; assert( offset_left + 1 < (int)line.size() ); int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width; assert( offset_right < (int)line.size() ); line[offset_left + 1] = '/'; line[offset_right + 0] = '\\'; } }; //int main() //{ // MaxHeap<int> maxheap = MaxHeap<int>(100); //！创建带初始值堆的写法！ // srand((unsigned int)time(NULL)); // for(int i= 0; i<31; i++){ // maxheap.Insert(rand()0); // } // // maxheap.testPrint(); // while(!maxheap.IsEmpty()){ // cout<< maxheap.ExtractMax()<<" "; // } // while(1); // return 0; //}然后怎样利用这种堆的入队出队进行排序呢？你会发现这种最大堆的根节点一定是数组中的最大值，并且你每次取走根节点之后，又会把数组剩下的数中的最大值选出来放到根节点上，这样每次取出根节点就能进行排序了，下面是第一种排序的代码： 先把前面的入队出队程序放到heap1.h文件中，然后利用堆的函数进行排序。
#include"Heap1.h" template<typename T> void heap_sort(T arr[], int n){ MaxHeap<int> maxheap = MaxHeap<int>(n); //！创建带初始值堆的写法！ for(int i= 0; i<n; i++){ maxheap.Insert(arr[i]); } for(int i= n-1; i>=0; i--){ arr[i]=maxheap.ExtractMax(); } } int main() { int n=7; int arr[7]={7,5,10,4,2,3,0}; heap_sort(arr,n); for(int k=0; k<n; k++) { //cout<<"排序后："<<endl; cout<<arr[k]<<" "; } while(1); return 0; }上面是一种排序方法，还有一种排序方法不需要入队，直接在构造函数的地方进行数组内部的整理。先把要排序得数组放到堆数组中，注意位置错开一位，然后它从第一个非叶子节点开始，第一个非叶子节点的求法是count/2，最大的元素个数除以2就是第一个非叶子节点，然后依次减减通过“下沉”把他们放到对应的位置，构成最大堆。
新的构造函数如下：
MaxHeap(Item arr[],int n){ //开辟一个临时数组 data=new Item[n+1];//!这里算上第0个不占用的空间是n+1! this->capacity = n; for(int k=0;k<n;k++){ data[k+1]=arr[k]; } count =n;//！元素个数要变化！！ //循环里是i--不是i/2 for(int i=count/2; i>0; i--){ shiftdown(i); } }面向对象的调用函数如下：
template<typename T> void heap_sort2(T arr[], int n){ MaxHeap<T> maxheap = MaxHeap<T>(arr,n); //！创建带初始值堆的写法！ for(int i= n-1; i>=0; i--){ arr[i]=maxheap.ExtractMax(); } }最后同样可以进行排序。这种叫heapify排序方式。
两种堆排序的区别在于：第一种就在初始构造函数中建了一个临时数组空间，然后靠往临时数组中插入和取出（或者说入队出队）得到最终有序数组。第二个heapify助排序是在构造函数里除了创建临时数组，还把所有元素放到临时数组中（注意临时数组第0位不放元素），并按照非叶子节点减减依次进行了排序。最后只需要依次取出堆顶元素即可。 一个插入的时候排序，一个全部放进去之后排序。一个面向对象要两个函数（插入取出）完成排序，一个面向对象只需要取出完成排序。第二种堆排序效果要好于第一种堆排序！ 将n个元素逐个插入到一个空堆中，算法复杂度是O（nlogn） heapifty的过程，算法复杂度为O（n）
排序仅仅是堆里面的一个小功能，堆最大的用处在于动态的数据维护！
原地堆排序是直接在原数组中先进行一波heapify助排序，但是原始数组并没有包含对第0个元素的处理，所以下沉的循环也变了，从2*k-1开始。
下沉排序的代码如下：
// 原始的shiftDown过程 template<typename T> //这里的k代表数组下标为k的非叶子节点 void __shiftDown(T arr[], int n, int k){ //几乎和shiftdown一样，不过是把2*k换成2*k+1,因为从0开始嘛 while( 2*k+1 < n ){ int j = 2*k+1; if( j+1 < n && arr[j+1] > arr[j] ) j += 1; if( arr[k] >= arr[j] )break; swap( arr[k] , arr[j] ); k = j; } } // 优化的shiftDown过程, 使用赋值的方式取代不断的swap, // 该优化思想和我们之前对插入排序进行优化的思路是一致的 template<typename T> void __shiftDown2(T arr[], int n, int k){ T e = arr[k]; while( 2*k+1 < n ){ int j = 2*k+1; if( j+1 < n && arr[j+1] > arr[j] ) j += 1; if( e >= arr[j] ) break; arr[k] = arr[j]; k = j; } arr[k] = e; }最后一个元素的索引 = n-1，因为从0开始，用它求第一个非叶子节点也变成了(n-1-1)/2 在面向对象的函数中的使用：
// 不使用一个额外的最大堆, 直接在原数组上进行原地的堆排序 template<typename T> void heapSort(T arr[], int n){ // 注意，此时我们的堆是从0开始索引的 // 从(最后一个元素的索引-1)/2开始 // 最后一个元素的索引 = n-1，因为从0开始，用它求第一个非叶子节点也变成了(n-1-1)/2 //从第一个非叶子节点开始，对所有非叶子节点下沉之后，数组就会变成最大堆 for( int i = (n-1-1)/2 ; i >= 0 ; i -- ) __shiftDown2(arr, n, i); //其实下面直接用提取函数就可以，但是因为不能借用其他数组 for( int i = n-1; i > 0 ; i-- ){ //把最大的数放到最后，就把它放在了正确的位置， swap( arr[0] , arr[i] ); //对仅一次变化后的最大堆再进行下沉，又会变成新的最大堆 __shiftDown2(arr, i, 0); } }上面建立的堆，如果看成一个个任务的话，有一个问题就是，要是想找出某一个任务不好找，因为他们的位置都在变动，每次必须从头遍历一下才能找到你需要的那个任务，这样太麻烦，于是就有人想出来，要不不要让任务变来变去，他们不动，让他们的替身，也就是用初始位置的编号作为一个索引，让这些索引代替原数值动。所以后面所有的最大堆，最大值都变成了索引，你想要知道原值是什么，把索引输进去作为编号就得到。于是产生了索引堆。
添加索引之后的代码如下： /在下沉、上升、插入、删除的函数中，都要把以前的交换函数换成替代数组的交换函数，把条件比较换成index的下标 /然后 1.多了一个返回最大索引的函数、 2.多了一个根据索引返回用户值的函数 3.多了一个根据索引值修改任务值的函数
#include<iostream> using namespace std;//没有上面头文件std会报错！ #include<ctime> #include<cassert>//等于#include<assert.h> #include <algorithm> #include <string> #include <cmath> //在下沉、上升、插入、删除的函数中，都要把以前的交换函数换成替代数组的交换函数，把条件比较换成index的下标 //然后1.还多了一个返回最大索引的函数 2.多了一个根据索引返回用户值的函数 3.多了一个根据索引值修改任务内容 template<typename Item> class MaxHeap { private: Item *data;//数组指针 Item *Index; int count;//数组元素个数 int capacity; void shiftup(int k){ //如果该该节点值比父节点大，就把他俩交换一下，注意k>1!! //!注意是while不是if! //比较还是比较原数组，但是交换就要换成替换数组 while(k>1 && data[Index[k/2]]<data[Index[k]]){ swap(Index[k/2],Index[k]); k/=2; } } void shiftdown(int k){ //下沉的前提条件是必须要有孩子 while(2*k<=count){ int j=2*k; //先比较两个子节点大小 if(data[Index[j]]<data[Index[j+1]] && j+1<=count){ j= j+1; } //遇到while循环就要先找到停止条件 if(data[Index[k]]>=data[Index[j]])//!if里的条件不是<! break; swap(Index[k],Index[j]); k=j;//!不是k*2! //下面这样写是错误的，如果父节点不小于子节点的情况下， 就不会跳出了，陷入死循环 //if(data[k]<data[j])//!if里的条件不是<! //{ // swap(data[k],data[j]); // k=j;//!不是k*2! //} } //再跟父节点进行比较 } public: //构造函数 MaxHeap(int capacity){ //开辟一个临时数组 data=new Item[capacity+1];//!注意中括号前面的写法! Index=new Item[capacity+1]; count = 0;//初始化元素个数 this->capacity = capacity; } MaxHeap(Item arr[],int n){ //开辟一个临时数组 data=new Item[n+1];//!这里算上第0个不占用的空间是n+1! this->capacity = n; for(int k=0;k<n;k++){ data[k+1]=arr[k]; } count =n;//！元素个数要变化！！ //循环里是i--不是i/2 for(int i=count/2; i>0; i--){ shiftdown(i); } } ~MaxHeap() { delete[] data; delete[] Index; } int size()//获取元素个数 { return count; } bool IsEmpty() { return count==0; } void Insert(int i,Item item)//入队插入函数 { assert(count+1<=capacity);//判断要放置的位置有没有越界 assert(i>=1 && i<=capacity); //替代数组Index在末尾加上添加的下标 //真正的数组就在在另一个数组新下标下面添加上对应的值 i+=1; Index[count+1]=i; data[i] = item;//把新元素插入数组中 count++;//元素个数加1 shiftup(count);//把元素上移到对应位置，注意该函数放在私有位置，不对用户开放 } int ExtractMax(){ assert(count>0);//取最大值的时候保证不是第0个 Item ret = data[Index[1]]; swap(Index[1],Index[count]); count--;//取出来之后要记得减去 shiftdown(1); return ret; } //返回最大索引 int Index_ExtractMax(){ assert(count>0);//取最大值的时候保证不是第0个 int ret = Index[1]-1;//最大索引要减一，因为从外部来看是从0开始的 swap(Index[1],Index[count]); count--;//取出来之后要记得减去 shiftdown(1); return ret; } //返回索引对应用户值 Item getItem(int i){ return data[i+1];//对用户来说是从0开始的 } //改变用户的值 void change(int i, Item newItem){ i+=1; data[i]=newItem; //找到替身数组中对应的下标值，然后 if(int j=0;j<count;j++){ if(Index[j]==i){ //我刚开始觉得下面得操作多此一举，替身数组得下标又没有改变，没必要挪动他们得位置 //后来明白了，原数组变了，替身得位置是一定要变得！下沉上升操作都是针对原数组的，替身在上升下沉的过程中只是作为下标的存在。 shiftdown(j); shiftup(j); return； } } } public: // 以树状打印整个堆结构 void testPrint(){ // 我们的testPrint只能打印100个元素以内的堆的树状信息 if( size() >= 100 ){ cout<<"This print function can only work for less than 100 int"; return; } // 我们的testPrint只能处理整数信息 if( typeid(Item) != typeid(int) ){ cout <<"This print function can only work for int item"; return; } cout<<"The max heap size is: "<<size()<<endl; cout<<"Data in the max heap: "; for( int i = 1 ; i <= size() ; i ++ ){ // 我们的testPrint要求堆中的所有整数在[0, 100)的范围内 assert( data[i] >= 0 && data[i] < 100 ); cout<<data[i]<<" "; } cout<<endl; cout<<endl; int n = size(); int max_level = 0; int number_per_level = 1; while( n > 0 ) { max_level += 1; n -= number_per_level; number_per_level *= 2; } int max_level_number = int(pow(2.0, max_level-1)); int cur_tree_max_level_number = max_level_number; int index = 1; for( int level = 0 ; level < max_level ; level ++ ){ string line1 = string(max_level_number*3-1, ' '); int cur_level_number = min(count-int(pow(2.0,level))+1,int(pow(2.0,level))); bool isLeft = true; for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){ putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft ); isLeft = !isLeft; } cout<<line1<<endl; if( level == max_level - 1 ) break; string line2 = string(max_level_number*3-1, ' '); for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ ) putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 ); cout<<line2<<endl; cur_tree_max_level_number /= 2; } } private: void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){ int sub_tree_width = (cur_tree_width - 1) / 2; int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width; assert(offset + 1 < (int)line.size()); if( num >= 10 ) { line[offset + 0] = '0' + num / 10; line[offset + 1] = '0' + num % 10; } else{ if( isLeft) line[offset + 0] = '0' + num; else line[offset + 1] = '0' + num; } } void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){ int sub_tree_width = (cur_tree_width - 1) / 2; int sub_sub_tree_width = (sub_tree_width - 1) / 2; int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width; assert( offset_left + 1 < (int)line.size() ); int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width; assert( offset_right < (int)line.size() ); line[offset_left + 1] = '/'; line[offset_right + 0] = '\\'; } }; //int main() //{ // MaxHeap<int> maxheap = MaxHeap<int>(100); //！创建带初始值堆的写法！ // srand((unsigned int)time(NULL)); // for(int i= 0; i<31; i++){ // maxheap.Insert(rand()0); // } // // maxheap.testPrint(); // while(!maxheap.IsEmpty()){ // cout<< maxheap.ExtractMax()<<" "; // } // while(1); // return 0; //}添加一个反向数组，里面保存每一个下标（除了0）在替身中的位置。 有如下特性：
代码中对每一次替身的交换都进行了反向数组的优化交换，最终实现对修改堆中数值函数的时间优化，让它从O（n*n）变成了O（1）。
#include<iostream> using namespace std;//没有上面头文件std会报错！ #include<ctime> #include<cassert>//等于#include<assert.h> #include <algorithm> #include <string> #include <cmath> //在下沉、上升、插入、删除的函数中，都要把以前的交换函数换成替代数组的交换函数，把条件比较换成index的下标 //然后1.还多了一个返回最大索引的函数 2.多了一个根据索引返回用户值的函数 3.多了一个根据索引值修改任务内容 template<typename Item> class MaxHeap { private: Item *data;//数组指针 Item *Index; Item *rev; int count;//数组元素个数 int capacity; void shiftup(int k){ //如果该该节点值比父节点大，就把他俩交换一下，注意k>1!! //!注意是while不是if! //比较还是比较原数组，但是交换就要换成替换数组 while(k>1 && data[Index[k/2]]<data[Index[k]]){ swap(Index[k/2],Index[k]); k/=2; } } void shiftdown(int k){ //下沉的前提条件是必须要有孩子 while(2*k<=count){ int j=2*k; //先比较两个子节点大小 if(data[Index[j]]<data[Index[j+1]] && j+1<=count){ j= j+1; } //遇到while循环就要先找到停止条件 if(data[Index[k]]>=data[Index[j]])//!if里的条件不是<! break; swap(Index[k],Index[j]); rev[Index[k]] = k; rev[Index[j]] = j; k=j;//!不是k*2! //下面这样写是错误的，如果父节点不小于子节点的情况下， 就不会跳出了，陷入死循环 //if(data[k]<data[j])//!if里的条件不是<! //{ // swap(data[k],data[j]); // k=j;//!不是k*2! //} } //再跟父节点进行比较 } public: //构造函数 MaxHeap(int capacity){ //开辟一个临时数组 data=new Item[capacity+1];//!注意中括号前面的写法! Index=new Item[capacity+1]; rev =new Item[capacity+1]; count = 0;//初始化元素个数 this->capacity = capacity; } MaxHeap(Item arr[],int n){ //开辟一个临时数组 data=new Item[n+1];//!这里算上第0个不占用的空间是n+1! this->capacity = n; for(int k=0;k<n;k++){ data[k+1]=arr[k]; } count =n;//！元素个数要变化！！ //循环里是i--不是i/2 for(int i=count/2; i>0; i--){ shiftdown(i); } } ~MaxHeap() { delete[] data; delete[] Index; delete[] rev; } int size()//获取元素个数 { return count; } bool IsEmpty() { return count==0; } void Insert(int i,Item item)//入队插入函数 { assert(count+1<=capacity);//判断要放置的位置有没有越界 assert(i>=1 && i<=capacity); //替代数组Index在末尾加上添加的下标 //真正的数组就在在另一个数组新下标下面添加上对应的值 i+=1; Index[count+1]=i; rev[i]=count+1;//优化 data[i] = item;//把新元素插入数组中 count++;//元素个数加1 shiftup(count);//把元素上移到对应位置，注意该函数放在私有位置，不对用户开放 } int ExtractMax(){ assert(count>0);//取最大值的时候保证不是第0个 Item ret = data[Index[1]]; swap(Index[1],Index[count]); //优化 rev[Index[1]] = 1; rev[Index[count]] = 0;//这里有点晕！！！ count--;//取出来之后要记得减去 shiftdown(1); return ret; } //返回最大索引 int Index_ExtractMax(){ assert(count>0);//取最大值的时候保证不是第0个 int ret = Index[1]-1;//最大索引要减一，因为从外部来看是从0开始的 swap(Index[1],Index[count]); //优化 rev[Index[1]] = 1; rev[Index[count]] = 0;//因为要把这个对应的元素删除 count--;//取出来之后要记得减去 shiftdown(1); return ret; } bool contain(int i){ assert(i+1>=1 && i+1<=capacity); return rev[i+1]!=0;//只有下标不在替身数组的时候才为0 } //返回索引对应用户值 Item getItem(int i){ assert(contain(i));//为了保证这个i在替身数组中 return data[i+1];//对用户来说是从0开始的 } //改变用户的值 void change(int i, Item newItem){ assert(contain(i)); i+=1; data[i]=newItem; //找到替身数组中对应的下标值，然后 //if(int j=0;j<count;j++){ //if(Index[j]==i){ int j=rev[i]; //我刚开始觉得下面得操作多此一举，替身数组得下标又没有改变，没必要挪动他们得位置 //后来明白了，原数组变了，替身得位置是一定要变得！下沉上升操作都是针对原数组的，替身在上升下沉的过程中只是作为下标的存在。 shiftdown(j); shiftup(j); return； //} //} } public: // 以树状打印整个堆结构 void testPrint(){ // 我们的testPrint只能打印100个元素以内的堆的树状信息 if( size() >= 100 ){ cout<<"This print function can only work for less than 100 int"; return; } // 我们的testPrint只能处理整数信息 if( typeid(Item) != typeid(int) ){ cout <<"This print function can only work for int item"; return; } cout<<"The max heap size is: "<<size()<<endl; cout<<"Data in the max heap: "; for( int i = 1 ; i <= size() ; i ++ ){ // 我们的testPrint要求堆中的所有整数在[0, 100)的范围内 assert( data[i] >= 0 && data[i] < 100 ); cout<<data[i]<<" "; } cout<<endl; cout<<endl; int n = size(); int max_level = 0; int number_per_level = 1; while( n > 0 ) { max_level += 1; n -= number_per_level; number_per_level *= 2; } int max_level_number = int(pow(2.0, max_level-1)); int cur_tree_max_level_number = max_level_number; int index = 1; for( int level = 0 ; level < max_level ; level ++ ){ string line1 = string(max_level_number*3-1, ' '); int cur_level_number = min(count-int(pow(2.0,level))+1,int(pow(2.0,level))); bool isLeft = true; for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index ++ , index_cur_level ++ ){ putNumberInLine( data[index] , line1 , index_cur_level , cur_tree_max_level_number*3-1 , isLeft ); isLeft = !isLeft; } cout<<line1<<endl; if( level == max_level - 1 ) break; string line2 = string(max_level_number*3-1, ' '); for( int index_cur_level = 0 ; index_cur_level < cur_level_number ; index_cur_level ++ ) putBranchInLine( line2 , index_cur_level , cur_tree_max_level_number*3-1 ); cout<<line2<<endl; cur_tree_max_level_number /= 2; } } private: void putNumberInLine( int num, string &line, int index_cur_level, int cur_tree_width, bool isLeft){ int sub_tree_width = (cur_tree_width - 1) / 2; int offset = index_cur_level * (cur_tree_width+1) + sub_tree_width; assert(offset + 1 < (int)line.size()); if( num >= 10 ) { line[offset + 0] = '0' + num / 10; line[offset + 1] = '0' + num % 10; } else{ if( isLeft) line[offset + 0] = '0' + num; else line[offset + 1] = '0' + num; } } void putBranchInLine( string &line, int index_cur_level, int cur_tree_width){ int sub_tree_width = (cur_tree_width - 1) / 2; int sub_sub_tree_width = (sub_tree_width - 1) / 2; int offset_left = index_cur_level * (cur_tree_width+1) + sub_sub_tree_width; assert( offset_left + 1 < (int)line.size() ); int offset_right = index_cur_level * (cur_tree_width+1) + sub_tree_width + 1 + sub_sub_tree_width; assert( offset_right < (int)line.size() ); line[offset_left + 1] = '/'; line[offset_right + 0] = '\\'; } }; //int main() //{ // MaxHeap<int> maxheap = MaxHeap<int>(100); //！创建带初始值堆的写法！ // srand((unsigned int)time(NULL)); // for(int i= 0; i<31; i++){ // maxheap.Insert(rand()0); // } // // maxheap.testPrint(); // while(!maxheap.IsEmpty()){ // cout<< maxheap.ExtractMax()<<" "; // } // while(1); // return 0; //}上述所有的就是优先队列，可以用于游戏设计，排序，归并排序的多路排序等很多地方。
