队列sqaure根运行时的优先级
我正在进行数据结构考试，我正在准备一系列复习题。我的问题如下：
“假设你的朋友来找你，声称他发明了一个超快速的基于优先级的比较队列。优先级队列的速度如下（n 是当前在优先级队列中的项目数）：a. 在 O（sqrt（logn））时间插入新项目 b. 在 O（sqrt（logn）） 时间从队列中提取（删除并返回）最小项目。
解释为什么你的朋友一定在撒谎：
据我所知，标准优先级队列的运行时间是用于提取的O（1）和O（n）。我无法理解这个问题。任何帮助将不胜感激。
共有1个答案
O（1）和O（n）-它的未排序数组实现，但您可以对队列进行排序或部分排序（例如二进制堆）。二进制堆的最佳实现是插入或选择O（log（N））。但对于某些特殊情况，可以达到O（log（N）^1/2）或甚至loglog（N）-例如整数。但如果你的朋友没有说任何关于set的话，那就是他撒谎的原因。
-
我试图实现Dijkstra算法的一个版本，以找到公共汽车从起点到终点的最短路线。不幸的是，我似乎找不到swift提供优先级队列类型的库或其他方式，所以我似乎必须自己编写代码。 话虽如此，有人能指出我做这件事的正确方向吗？ 目前我的想法如下： 到目前为止这是我的代码。似乎太短太残忍了...我一定是在概念上漏掉了什么。
-
我需要一个优先级队列，它首先获得具有最高优先级值的项目。我当前正在使用队列库中的PriorityQueue类。但是，这个函数只先返回值最小的项。我尝试了一些很难看的解决方案，比如（sys.maxint-priority）作为优先级，但我只是想知道是否存在更优雅的解决方案。
-
问题内容： 我正在尝试根据文档中提供的示例实现优先级队列。文件：priorityQueue 简而言之，它看起来像这样（不包括所有内容）： 该文件中： 如您所见，在与示例进行比较时，我不使用指针，因为这样做会给我一个编译错误，告诉我我的优先级队列未正确实现接口。 这会给我带来以下问题： 该项目未附加到队列中。 我试图写出队列指针地址，它显示了不同的地址。这就解释了为什么它不起作用，但是切片不是地图长
-
我正在实现一个应用程序，该应用程序根据曼哈顿距离查找（x，y）平面中给定位置的最近n个事件。我使用最大优先级队列来存储找到的事件，并使用曼哈顿距离比较器。这个队列应该总是有最大人距离事件作为它的窥视，但是我发现这不会一直发生。我在循环中使用pq.poll（）打印了这个队列的结果，我发现队列在删除后没有重新排列，只是有时。 我的比较者： 以主方法打印： 输出： 如您所见，事件不是按降序排列的！然而，
-
注意：我知道可以用比较器创建优先级队列，然后重复调用Add。
-
考虑下面的优先级类声明<代码>类优先级队列 我的想法： 我能想到的一件事是，这将强制优先级队列使用对象比较器，并且不会提供实现其自定义比较器的能力，因为类的用户可能希望基于某个不同的比较器构建队列。