学步园

#include <iostream><br /> using namespace std;<br /> int heap_size;<br /> int length;<br /> //左孩子<br /> int Left(int i)<br /> {<br /> return 2*i+1;<br /> }<br /> //右孩子<br /> int Right(int i)<br /> {<br /> if(2*(i+1) <= length -1)<br /> {<br /> return 2*(i+1);<br /> }<br /> else<br /> {<br /> return -1;<br /> }<br /> }<br /> //交换两个值<br /> void swap(int &a, int &b)<br /> {<br /> int c = a;<br /> a = b;<br /> b = c;<br /> }<br /> void Max_Heapify(int *A,int i)<br /> {<br /> int l = Left(i);<br /> int r = Right(i);<br /> int largest = i;<br /> if(l <= heap_size && A[l] > A[i])<br /> {<br /> largest = l;<br /> }<br /> if(r != -1 && r <= heap_size && A[r]>A[largest])<br /> {<br /> largest = r;<br /> }<br /> if(largest != i)<br /> {<br /> swap(A[i],A[largest]);<br /> Max_Heapify(A,largest);<br /> }<br /> }<br /> //建堆<br /> void Build_Max_Heap(int *A)<br /> {<br /> for(int i=length/2; i >= 0; i--)<br /> {<br /> Max_Heapify(A,i);<br /> }<br /> }<br /> //堆排序<br /> void Heap_Sort(int *A)<br /> {<br /> Build_Max_Heap(A);<br /> for(int i = length-1;i >=0; i--)<br /> {<br /> swap(A[0],A[i]);<br /> heap_size --;<br /> Max_Heapify(A,0);<br /> }<br /> }<br /> void printArray(int *A)<br /> {<br /> for(int i = 0; i < length; ++i)<br /> {<br /> cout << A[i] <<" ";<br /> }<br /> }<br /> int main()<br /> {<br /> int array[]={16,14,10,8,7,9,3,2,4,1};<br /> length = sizeof(array)/sizeof(int);<br /> heap_size = length-1;<br /> Heap_Sort(array);<br /> printArray(array);<br /> cout <<endl;<br /> return 0;<br /> }<br />