优先队列的时间复杂度

2023-12-15 16:07:50

优先队列的时间复杂度?

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

优先队列是什么?

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

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

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

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

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

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

堆的时间复杂度

pushpoptopempty
O(log n)O(log n)O(1)O(1)

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

文章来源:https://blog.csdn.net/guigenyi/article/details/135017424
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。