🔥码云GVP开源项目 12k star Uniapp+ElementUI 功能强大 支持多语言、二开方便! 广告
## 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; } ~~~ 单次运行结果: 自底向上: ![](https://box.kancloud.cn/2016-01-24_56a421213c4d8.gif) 自顶向下: ![](https://box.kancloud.cn/2016-01-24_56a421214d217.gif)