1private:2enum{HEAP_DEFAULT_SIZE=10};//默认数组空间为Type*heap;//堆的数组名称4intcapacity;//堆空间大小5intsize;//有效元素个数2、小堆根据一组无序的数字创建小堆--最后实现堆排！C++中创建小堆，可以通过构造函数一次性创建；也可以调用插入函数创建小堆。小堆：堆顶的数据最小。一些方法的实现：(1)、删除函数，作用：每次删除堆顶，拿最后一个元素放到堆顶，在向下调整成小堆，这样就成升序输出了；
1boolremove(Typev){2if(size==0){3returnfalse;4}5v=heap[0];6heap[0]=heap[size-1];7size--;8siftDown(0,size-1);returntrue;11}(2)、插入函数，作用：向上构建小堆
1boolinsert(constTypex){2if(sizecapacity){3returnfalse;4}5heap[size]=x;6siftUp(size);7size++;8returntrue;9}(3)、一次向下调整函数，作用：向下构建小堆
1voidsiftDown(intstart,intend){2inti=start;3intj=2*i+1;45Typetmp=heap[i];6while(j=end){7if(j+1=endheap[j]heap[j+1]){8j=j+1;9}10if(tmpheap[j]){11heap[i]=heap[j];//要是写交换函数的话，太浪费内存空间！！12}else{13break;14}15i=j;16j=2*i+1;17}18heap[i]=tmp;19}(4)、一次向上调整函数
1voidsiftUp(intstart){2intj=start;3inti=(j-1)/2;//父结点,这里的求法要注意。45Typetmp=heap[j];//保存的是要插入的数据6while(j0){7if(heap[i]tmp){8heap[j]=heap[i];9}else{10break;11}j=i;14i=(j-1)/2;15}16heap[j]=tmp;17}小堆的完整程序：
1#ifndef_MIN_HEAP_H_2#define_MIN_HEAP_H_34#includeiostream5usingnamespacestd;67templatetypenameType8classMinHeap{9public:10MinHeap(intsz=HEAP_DEFAULT_SIZE){11capacity=szHEAP_DEFAULT_SIZE?sz:HEAP_DEFAULT_SIZE;12heap=newType[capacity];13size=0;14}15MinHeap(Typear[],intn){16capacity=nHEAP_DEFAULT_SIZE?n:HEAP_DEFAULT_SIZE;17heap=newType[capacity];18size=n;for(inti=0;in;i++){21heap[i]=ar[i];22}intcurPos=n/2-1;//从最后一个非叶子结点开始调整，25while(curPos=0){26siftDown(curPos,n-1);27curPos--;//一直调整到根结点28}29}30~MinHeap(){31delete[]heap;32heap=NULL;33capacity=size=0;34}35public:36boolremove(Typev){37if(size==0){38returnfalse;39}40v=heap[0];41heap[0]=heap[size-1];42size--;43siftDown(0,size-1);returntrue;46}47boolinsert(constTypex){48if(sizecapacity){49returnfalse;50}51heap[size]=x;52siftUp(size);53size++;54returntrue;55}56voidshowHeap()const{57for(inti=0;isize;i++){58coutheap[i]"";59}60coutendl;61}62protected:63voidsiftDown(intstart,intend){64inti=start;//父结点65intj=2*i+1;//子节点(左孩子)Typetmp=heap[i];68while(j=end){69if(j+1=endheap[j]heap[j+1]){70j=j+1;71}72if(tmpheap[j]){73heap[i]=heap[j];//要是写交换函数的话，太浪费内存空间！！采用了直接覆盖的方法。74}else{75break;76}77i=j;78j=2*i+1;79}80heap[i]=tmp;81}82voidsiftUp(intstart){83intj=start;84inti=(j-1)/2;//父结点,这里的求法要注意。Typetmp=heap[j];87while(j0){88if(heap[i]tmp){89heap[j]=heap[i];90}else{91break;92}j=i;95i=(j-1)/2;96}97heap[j]=tmp;98}99private:enum{HEAP_DEFAULT_SIZE=10};Type*heap;intcapacity;intsize;};#endif测试程序：
1#include"minHeap.h"23intmain(void){4intar[]={53,17,78,9,45,65,87,23,};5intn=sizeof(ar)/sizeof(int);6inti;7MinHeapinthp;8//MinHeapinthp(ar,n);9for(i=0;in;i++){10hp.insert(ar[i]);11}12hp.showHeap();intvalue;15for(i=0;in;i++){16hp.remove(value);17coutvalue"";18}19coutendl;20return0;21}测试结果：3、大堆--降序思想和小堆差不多，具体也不再分析了；代码如下：
1#ifndef_MAX_HEAP_H_2#define_MAX_HEAP_H_34#includeiostream5usingnamespacestd;67templatetypenameType8classMaxHeap{9public:10MaxHeap(intsz=DEFAULT_HEAP_SIZE){11capacity=szDEFAULT_HEAP_SIZE?sz:DEFAULT_HEAP_SIZE;12heap=newType[capacity];13size=0;14}15MaxHeap(intar[],intn){16capacity=nDEFAULT_HEAP_SIZE?n:DEFAULT_HEAP_SIZE;17heap=newType[capacity];18size=n;19for(inti=0;in;i++){20heap[i]=ar[i];21}intcurPos=n/2-1;24while(curPos=0){25siftDown(curPos,size-1);26curPos--;27}}30~MaxHeap(){}31public:32boolinsert(constTypex){33if(sizecapacity){34returnfalse;35}36heap[size]=x;37siftUp(size);38size++;returntrue;41}42voidremove(intvalue){43value=heap[0];44heap[0]=heap[size-1];45size--;46siftDown(0,size-1);47}48voidshowHeap(){49for(inti=0;isize;i++){50coutheap[i]"";51}52coutendl;53}54protected:55voidsiftDown(intstart,intend){56inti=start;57intj=2*i+1;58inttmp=heap[i];59while(j=end){60if(j+1=endheap[j]heap[j+1]){61j=j+1;62}if(heap[j]tmp){65heap[i]=heap[j];66}else{67break;68}69i=j;70j=2*i+1;71}72heap[i]=tmp;73}74voidsiftUp(intstart){75intj=start;76inti=(j-1)/2;Typetmp=heap[j];79while(j0){80if(heap[i]tmp){81heap[j]=heap[i];82}else{83break;84}85j=i;86i=(j-1)/2;87}88heap[j]=tmp;89}90private:91enum{DEFAULT_HEAP_SIZE=10};92Type*heap;93intcapacity;94intsize;95};#endif测试代码：
1#include"maxHeap.h"23intmain(void){4intar[]={23,45,12,6,4,9,33,};5intn=sizeof(ar)/sizeof(int);6inti;78MaxHeapinthp;9for(i=0;in;i++){10hp.insert(ar[i]);11}12hp.showHeap();intvalue;15for(i=0;in;i++){16hp.remove(value);17coutvalue"";18}19coutendl;return0;23}测试结果：推荐阅读：从零开始学习数据结构--入门篇从零开始学习数据结构--链表从零开始学习数据结构--线性表从零开始学习数据结构--栈从零开始学习数据结构--队列从零开始学习数据结构--矩阵+串从零开始学习数据结构--哈希表从零开始学习数据结构--散列桶从零开始学习数据结构--二叉树
从零开始学习数据结构--二叉树方法实现
从零开始学习数据结构--线索二叉树从零开始学习数据结构--树、森林与二叉树的转换
认真的人自带光芒谱戈一辈子很长，要和有趣的人在一起