堆排序

堆排序

1. 把无序数组构建成二叉堆
2. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶

void DownAdjust(vector<int>& A, int parentIndex, int len) { int temp = A[parentIndex];

int childIndex = 2 * parentIndex + 1;

while(childIndex < len) { if(childIndex + 1 < len && A[childIndex + 1] < A[childIndex])

childIndex++;

if(temp >= A[childIndex]) break;

A[parentIndex] = A[childIndex];

parentIndex = childIndex;

childIndex = 2 * childIndex + 1;

} A[parentIndex] = temp;

} void HeapSort( vector<int>& A) {

int len = A.size();

if(len <= 1) return;

for(int i = len / 2; i >= 0; i--) { DownAdjust(A, i, len);

}

for(int i = len- 1; i > 0; i--) { int temp = A[i];

A[i] = A[0];

A[0] = temp;

DownAdjust(A, 0 , i);

} }

最短路径问题

多源最短路径

得出图中任意两个顶点之间的最短路径

Floyd算法：