我们知道dijkstra算法的时间复杂度是O(N^2)，外层循环松弛的次数，N个点要松弛N-1次为O(N)，而内层循环是遍历dis数组每次找到距离顶点最小的点，时间复杂度也是O(N)，堆优化就是优化这一过程降为O(logN)，如果M(边)远小于N^2储存图用邻接表，这样优化的总时间复杂度为(N+M)logN，堆优化需要3个数组：

1.dis数组记录单源顶点到其余点的距离

2.h数组是一个最小堆，堆里面存储的是顶点编号(注意：h数组不是按照编号大小来建立最小堆的，而是按照顶点在数组dis中对应的值来建立这个最小堆)

3.此外还需要一个pos数组来记录每个顶点在最小堆中的位置

堆：简单理解为一颗特殊的完全二叉树，所有父结点都小于子结点的完全二叉树叫最小堆，相反叫最大堆

 下面一个根据题目来看具体如何实现堆优化版本的dijkstra算法

洛谷 P4779 【模板】单源最短路径（标准版）

题目描述

给定一个 n 个点，m 条有向边的带非负权图，请你计算从 s 出发，到每个点的距离。

数据保证你能从 s 出发到任意点。

输入格式

第一行为三个正整数 n,m,s。 第二行起 m 行，每行三个非负整数 ui​,vi​,wi​，表示从 ui​ 到 vi​ 有一条权值为 wi​ 的有向边。

输出格式

输出一行 n 个空格分隔的非负整数，表示 s 到每个点的距离。

输入输出样例

输入 #1

4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 4 4

输出 #1

0 2 4 3

说明/提示

样例解释请参考 数据随机的模板题。

1≤n≤10^5；

1≤m≤2×10^5；

s=1；

1≤ui​,vi​≤n；

0≤wi​≤10^9,

0≤∑wi​≤10^9。

本题数据可能会持续更新，但不会重测，望周知。

2018.09.04 数据更新 from @zzq

 从题目的数据可以看到n最大为10^5如果不优化n^2肯定是过不了的，这就需要堆优化了，堆优化过程代码注释很详细。

#include<stdio.h>
//h数组保存堆，pos数组存储每个顶点在堆中的位置，book数组标记单源顶点到哪些点距离已经最短
int dis[100001], h[100001], pos[100001], book[100001], first[100001];
int n, m, s, size;//size为堆的大小
struct nb {int u, v, w, next;
}a[200001];//存储每一条边
//交换函数，用来交换堆中的两个元素的值
void swap(int x, int y)
{int t = h[x];h[x] = h[y]; h[y] = t;t = pos[h[x]]; pos[h[x]] = pos[h[y]];pos[h[y]] = t;//同步更新pos
}
//堆向下调整函数
void siftdown(int x)//传入一个需要向下调整的结点编号
{int flag = 0, t;//flag用来标记是否需要继续向下调整while (2 * x <= size && flag == 0)//有左孩子{//比较i和它左孩子2*i在dis中的值，并用t记录值较小的结点编号if (dis[h[x]] > dis[h[2 * x]])t = 2 * x;elset = x;//如果有右孩子，再对右孩子进行讨论if (2 * x + 1 <= size)if (dis[h[t]] > dis[h[2 * x + 1]])//右孩子值更小，更新较小的结点编号t = 2 * x + 1;//如果发现最小的结点编号不是自己，说明子结点中有比父结点更小的if (t != x){swap(x, t);//交换它们x = t;//更新i为刚才与它交换的儿子结点的编号，方便接下来继续向下调整}elseflag = 1;//否则说明当前的父结点已经比两个子结点都要小了，不需要再向下调整了}
}
//从堆顶取出一个元素
int pop()
{int t;t = h[1];//临时变量记录堆顶的值h[1] = h[size];//将堆的最后一个点赋值到堆顶pos[h[1]] = 1;size--;//堆的元素减少1siftdown(1);//向下调整，维护最小堆return t;//返回之前记录的堆顶元素
}
void siftup(int x)//传入一个需要向上调整的结点编号i
{int flag = 0;//用来标记是否需要继续向上调整while (x != 1 && flag == 0){//判断是否比父结点的小if (dis[h[x]] < dis[h[x / 2]])swap(x, x / 2);//交换它和它爸爸的位置elseflag = 1;//表示已经不需要调整了x = x / 2;//更新编号i为它父结点的编号，从而便于下一次继续向上调整}
}
int main()
{int i, k, gg;//读入n，m和s，n表示顶点个数，m表示边的条数，s为单源顶点scanf("%d %d %d", &n, &m, &s);size = n;for (i = 1; i <= m; i++)//读入边并建立邻接表(链式向前星){scanf("%d %d %d", &a[i].u, &a[i].v, &a[i].w);a[i].next = first[a[i].u];first[a[i].u] = i;}//初始化dis数组，这里是s顶点到其余顶点的初始距离for (i = 1; i <= n; i++)dis[i] = 1e9;k = first[s]; dis[s] = 0; book[s] = 1;while (k != 0)//{dis[a[k].v] = a[k].w;k = a[k].next;}//初始化堆for (i = 1; i <= n; i++){h[i] = i; pos[i] = i;}for (i = n / 2; i >= 1; i--)siftdown(i);gg = pop();//先弹出s顶点的元素for (i = 1; i < n; i++){gg = pop(); book[gg] = 1;//扫描当前顶点gg的所有的边，再以gg为中间结点，进行松弛k = first[gg];while (k != 0){if (book[a[k].v] == 0 && dis[a[k].v] > dis[gg] + a[k].w){dis[a[k].v] = dis[gg] + a[k].w;siftup(pos[a[k].v]);}k = a[k].next;}}for (i = 1; i <= n; i++)//输出答案printf("%d ", dis[i]);return 0;
}