## STL經典算法集錦<二>之堆算法 堆算法主要包括建立最大堆和堆排序算法。所使用建堆的數組將以0開始存儲數據。 下面將以兩種方法建堆：自底向上的建堆（STL和算法導論中使用到的）、自頂向下建堆（即插入建堆的方法） 公共操作： ~~~ int parent(int i) { return (int)((i-1)/2); } int left(int i) { return 2 * i+1; } int right(int i) { return (2 * i + 2); } ~~~ **版本一：自底向上** ~~~ void heapShiftDown(int heap[], int i, int heap_size) { int l = left(i); int r = right(i); int largest=i; //找出左右字節點與父節點中的最大者 if(l < heap_size && heap[l] > heap[largest]) largest = l; if(r < heap_size && heap[r] > heap[largest]) largest = r; //若最大者不為父節點，則需交換數據，并持續向下滾動至滿足最大堆特性 if(largest != i) { swap(heap[largest],heap[i]); heapShiftDown(heap, largest, heap_size); } } //自底向上的開始建堆，即從堆的倒數第二層開始 void buildHeap(int heap[],int heapSize) { for(int i = (heapSize-1)/2; i >= 0; i--) { heapShiftDown(heap, i, heapSize ); } } ~~~ **版本二：自頂向下的建堆** ~~~ //i為新插入節點的位置 void heapShiftUp(int heap[], int i) { int p=parent(i); //判斷插入新節點后是否滿足最大堆 //否則交換數據并持續向上滾動 if( heap[i] > heap[p]) { swap(heap[i],heap[p]); if(p != 0) heapShiftUp(heap,p); } } void buildHeap(int heap[],int heapSize) { //自第二層開始建堆 for(int i = 1; i < heapSize; i++) { heapShiftUp(heap, i); } } ~~~ **堆排序：** ~~~ void heapSort(int heap[], int heapSize ) { buildHeap(heap,heapSize); for(int i = heapSize- 1; i > 0; i--) { swap(heap[0],heap[i]); heapShiftDown(heap, 0, i); } } ~~~ **測試代碼：** ~~~ int main() { int len=20; int array[len]; srand(time(0)); for(int i=0;i<len;i++) array[i]=rand()%200; heapSort(array,len); for(int i=0;i<len;i++) cout<<array[i]<<"\t"; return 0; } ~~~ 單次運行結果： 自底向上：  自頂向下：