学步园

#include <iostream><br /> using namespace std;</p> <p>class MinHeap<br /> {<br /> private:<br /> int heapSize;//堆大小<br /> int *arr;//数组</p> <p>public:<br /> //构造函数<br /> MinHeap(int length)//传入数组初始化大小<br /> {<br /> this->heapSize=length;<br /> arr=new int[50];<br /> }<br /> //求父结点<br /> int parent(int i)<br /> {<br /> return i/2;<br /> }<br /> //求左孩子<br /> int left(int i)<br /> {<br /> return 2*i;<br /> }<br /> //求右孩子<br /> int right(int i)<br /> {<br /> return 2*i+1;<br /> }<br /> //交换函数<br /> void swap(int a,int b)<br /> {<br /> int temp=arr[a];<br /> arr[a]=arr[b];<br /> arr[b]=temp;<br /> }<br /> //维持堆性质函数,使用前提为左右子书均为最小堆<br /> void heapIfy(int i,int localHeapSize)<br /> {<br /> int l=left(i);<br /> int r=right(i);<br /> int least=i;<br /> //找出i,left(i),right(i)的最小值<br /> if(l<=localHeapSize&&arr[least]>arr[l])<br /> {<br /> least=l;<br /> }<br /> if(r<=localHeapSize&&arr[least]>arr[r])<br /> {<br /> least=r;<br /> }<br /> //交换arr[i],arr[largest]<br /> if(least!=i)<br /> {<br /> swap(i,least);<br /> heapIfy(least,localHeapSize);<br /> }<br /> }<br /> //初始化堆（建立堆）<br /> void buildHeap()<br /> {<br /> for(int i=heapSize/2;i>=1;i--)<br /> {<br /> heapIfy(i,heapSize);<br /> }<br /> }<br /> //堆排序<span class='wp_keywordlink'><a href="http://www.xuebuyuan.com/category/%E7%AE%97%E6%B3%95" title="算法" target="_blank">算法</a></span>（前提：堆已初始化）<br /> void heapSort()<br /> {<br /> int localHeapSize=heapSize;</p> <p> for(int i=heapSize;i>=2;i--)<br /> {<br /> swap(1,i);<br /> --localHeapSize;<br /> heapIfy(1,localHeapSize);<br /> }<br /> //倒置数组<br /> int i=1;<br /> int j=heapSize;<br /> while(i<j)<br /> {<br /> swap(i,j);<br /> ++i;<br /> --j;<br /> }</p> <p> }<br /> //去掉并返回堆中最小的元素（前提：堆已初始化）<br /> int extractMin()<br /> {<br /> if(heapSize>=1)<br /> {<br /> int min=arr[1];<br /> swap(1,heapSize);<br /> --heapSize;<br /> heapIfy(1,heapSize);<br /> return min;<br /> }<br /> else<br /> {<br /> cout<<"堆中没有元素"<<endl;<br /> return -1;<br /> }<br /> }<br /> //向堆中插入数据(前提：堆已经初始化)<br /> void heapInsert(int key)<br /> {<br /> ++heapSize;<br /> int i=heapSize;<br /> while(i>1&&arr[parent(i)]>key)<br /> {<br /> arr[i]=arr[parent(i)];<br /> i=parent(i);<br /> }<br /> arr[i]=key;<br /> }<br /> //输入数组<br /> void input()<br /> {<br /> int i=1;<br /> while(i<=heapSize)<br /> {<br /> cin>>arr[i];<br /> i++;<br /> }<br /> }<br /> //输出数组<br /> void display()<br /> {<br /> int i=1;<br /> while(i<=heapSize)<br /> {<br /> cout<<arr[i]<<" ";<br /> i++;<br /> }<br /> cout<<endl;<br /> }<br /> };</p> <p>void main()<br /> {<br /> //测试数据:10,9,8,7,6,5,4,3,2,1<br /> MinHeap test(10);//初始化的堆有10个元素<br /> test.input();//输入数据<br /> test.buildHeap();//初始化堆<br /> test.display();//打印初始化堆<br /> test.heapSort();//堆排序<br /> test.display();//打印排序结果<br /> test.buildHeap();//重新初始化堆<br /> test.heapInsert(8);//将8插入堆中<br /> test.display();//打印插入后结果<br /> test.heapSort();//重新排序<br /> test.display();//打印排序后结果<br /> test.extractMin();//删除最小元素<br /> test.display();//打印删除后结果<br /> test.heapSort();//删除后再次排序<br /> test.display();//输出删除后排序后结果</p> <p>}