## 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; } ~~~ 单次运行结果： 自底向上：  自顶向下：