优先队列的时间复杂度

优先队列的时间复杂度？

这个问题主要分为两个部分：优先队列是什么？优先队列的时间复杂度是多少？

优先队列是什么？

优先队列，英文名：Priority Queue。顾名思义，优先队列是一种特殊的队列，普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

优先队列是通过堆实现的，通过完全二叉树实现的小顶堆或大顶堆。

详情参考文章：c++优先队列(priority_queue)用法详解

优先队列的时间复杂度是多少？

优先队列用堆实现，只是需要构建初始堆，这个时间复杂度是O(n)插入和删除只是修改了堆顶和堆底，不需要所有的都排序，只是需要再次调整好堆。

堆的时间复杂度

因此，优先队列的时间复杂度为 O(log n)。