【数据结构】【堆排序】

这里是先建立最大堆&＃xff0c;再从小到大输出堆元素。具体实现及其解释见代码。

总结&＃xff1a;像这样支持插入元素和寻找最大&＃xff08;小&＃xff09;值元素的数据结构称为优先队列。堆就是优先队列的实现&＃xff0c;很大程度的降低了时间复杂度。

另外Dijkstra算法每次找离源点最近的一个顶点也可以用堆来优化&＃xff0c;使算法复杂度降到O((m&＃43;n)logn).具体实现见我另一篇博客堆排序实现dijsktra

用堆排序来优化prime算法见博客堆排序优化的prime算法

#includeint h[1000],n;//h是存放堆的数组&＃xff0c;n存放堆的结点个数
void swap(int x,int y)//交换函数
{int t;t &＃61; h[x];h[x] &＃61; h[y];h[y] &＃61; t;
}
void siftdown(int a)//向下调整函数
{//传入一个需要向下调整的结点编号a, 这里传入1&＃xff0c;即从堆的顶点开始向下调整 int t,flag &＃61; 0;//flag用来标记是否需要继续向下调整 while(a*2 <&＃61; n&&!flag){//当前结点至少得有左子结点 if(h[a] 2])//判断a和左子结点的关系&＃xff0c;t记录较大结点 t &＃61; a*2;elset &＃61; a;if(a*2&＃43;1 <&＃61; n)//如果它有右子结点&＃xff0c;再对右子结点进行讨论 {if(h[t] 2&＃43;1])t &＃61; a*2&＃43;1;}if(t!&＃61;a)//如果最大结点编号不是自己&＃xff0c;说明子结点中有比父结点更大的 {swap(t,a);//交换他们&＃xff0c;swap函数自己定义 a &＃61; t;//a更新为最大结点编号&＃xff0c;方便继续向下调整 }elseflag &＃61; 1;//最大结点编号是自己&＃xff0c;则不需要继续向下调整 }return;
}
void creat()//建立堆函数
{int i;for(i &＃61; n/2; i >&＃61; 1; i --)//从最后一个非叶结点到第一个结点依次向上调整 siftdown(i);return;
}
void heapsort()//堆排序
{while(n>0){swap(1,n);n--;siftdown(1);}return;
}
int main()
{int num,i;while(scanf("%d",&num)!&＃61;EOF){for(i &＃61;1; i <&＃61; num; i &＃43;&＃43;)scanf("%d",&h[i]);n &＃61; num;creat();//建堆 heapsort();//堆排序 for(i &＃61; 1; i <&＃61; num; i &＃43;&＃43;)//输出 printf("%d ",h[i]);printf("\n");}return 0;
}