【数据结构与算法】堆实现优先级队列

一.堆实现优先级队列的原理

堆就是可以将最大值或者最小值,每次取出,那么刚好可以进行排序,而我们的优先级队列,就是对于优先级最高的先进行出队,也就相当于是排序.

并且原来我们使用的是链队列来比较优先级,需要一个个的比较,如果我们采用堆,那么我们比较的次数就是log n,n为总的元素个数.
那么效率会高于链队列,所以我们采用对来实现优先级队列.

二.优先级队列结构体

用堆来实现优先级队列,完全就是堆的处理,只不过将堆数组的值改为队列的优先级就可以.

三.堆初始化

与堆的初始化无异.

遍历父节点:

向下比较调整:

四.入队

入队需要先判断是否已满

然后再进行插入:

然后插入后的数据,我们要进行向上比较:

五.出队

也是先判断是否为空:

然后进行数据删除:

同时对堆顶,进行向下调整.

六.销毁队列

有new就有delete进行销毁.

七.总结

用堆来实现优先级队列真是一种不错的选择!