时间戳

首页 > 解决方案 > 当我们可以更有效地使用向量来实现优先级队列时，为什么使用堆来实现它

c++ - 当我们可以更有效地使用向量来实现优先级队列时，为什么使用堆来实现它

问题描述

为什么在不使用堆的priority_queue情况下使用堆来实现我们可以只用向量来实现它。

假设我们使用向量作为队列并保持元素降序。我们可以将其用作优先队列。

对于插入：我们可以使用二分查找。Complexity O(logN)

删除：这里我们也可以使用二分查找。Complexity O(logN)

对于顶部元素：O(1)

此外，我们可以在O(1)短时间内访问第 k 个最大元素，而堆则不然。

那么，我们为什么要使用堆来实现优先级队列呢？

标签： c++stlpriority-queueimplementation

解决方案

对于插入：我们可以使用二分查找。复杂度 O(logN)

对于 deltion ：这里我们也可以使用二进制搜索。复杂度 O(logN)

不，你不能。通过使用排序的数组/向量，您只能搜索正确的索引，O(log N)但要执行实际的插入或删除，您必须移动其他元素，即O(N).

推荐阅读