复习下堆排序

[geminiwen]

http://blog.csdn.net/v_JULY_v/article/details/6198644
因为最近想要A一道题目，在#8 中提到过Floyd的最短路算法，它适用于多源最短路径的计算，但是不适用于其中提到题目的算法，因为其实提到的题目讲的是要求单源最短路径。单源最短路径一个典型的求法就是dijkstra算法，优化的方式，就是在松弛的时候从最小堆中抽取结点加入s集合。

做一段前奏，复习下堆排序。
首先这个堆其实是个完全二叉树。也就是说，结点的排布可以简单地用一个数组完全表示，堆排序说起来其实很简单，如果是最小堆，那么父节点的值是小于子节点的。如果是最大堆那么就是相反。

贴段刚刚写的小demo做注释吧。

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
#define MAX 101
int heap[MAX] = { 9,8,7,6,5,4,3,2,1,0 };

void simply_heap(int node,int len) { //递归更换堆中的位置
    int l = 2 * node + 1;
    int r = 2 * node + 2;
    int min_node;
    int t;
    if( l < len && heap[node] > heap[l] ) {
        min_node = l;
    } else {
        min_node = node;
    }

    if( r < len && heap[min_node] > heap[r] ) {
        min_node = r;
    }
        //以上工作是查找查找双亲节点和子节点中最小的那一个
    if( min_node != node ) {
        t = heap[node];
        heap[node] = heap[min_node];
        heap[min_node] = t;

        simply_heap(min_node,len);// 如果需要更改位置的话，那么顺便往下递归把子树中的结点也更新掉。
    }
}

void build_heap(int len) {
    for( int i = (len-1) / 2; i>=0 ; i-- ) {
        simply_heap(i,len);
    }
}

int main() {
    build_heap(10);
    for(int i = 0; i < 10; i++ ) {
        printf("%d\n",heap[i]);
    }
    system("pause");
    return 0;
}

堆的实际用例就是优先队列，在dijkstra算法中可以用来优化时间复杂度。
堆排序的信息：
时间复杂度：O(nlgn)...
//等同于归并排序
最坏：O(nlgn)
空间复杂度：O(1).
不稳定。