标签: priority-queue

什么更快:插入优先级队列,还是追溯排序？

我正在生成一些我需要在最后排序的项目.我想知道,在复杂性方面更快的是:将它们直接插入priority_queue或类似的数据结构中,还是在结尾处使用排序算法？

默认heapq是min队列实现,并想知道是否有最大队列选项？谢谢.

我尝试使用_heapify_max作为最大堆的解决方案,但是如何处理动态推/弹元素？似乎_heapify_max只能在初始化时使用.

import heapq

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])

编辑,尝试_heapify_max似乎不适用于动态推/弹元素.我尝试两种方法输出相同,两个输出都是,[0,1,2,3,4,5,6,7,8,9].

def heapsort(iterable):
    h = []
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

def heapsort2(iterable):
    h = []
    heapq._heapify_max(h)
    for value in iterable:
        heapq.heappush(h, value)
    return [heapq.heappop(h) for i in range(len(h))]

if __name__ == "__main__":

    print heapsort([1, 3, 5, …

更新:这是我实施的哈希定时轮.如果您有提高性能和并发性的想法,请告诉我.(20月- 2009年)

// Sample usage:
public static void main(String[] args) throws Exception {
    Timer timer = new HashedWheelTimer();
    for (int i = 0; i < 100000; i ++) {
        timer.newTimeout(new TimerTask() {
            public void run(Timeout timeout) throws Exception {
                // Extend another second.
                timeout.extend();
            }
        }, 1000, TimeUnit.MILLISECONDS);
    }
}

更新:我通过使用Hierarchical和Hashed Timing Wheels解决了这个问题.(19月- 2009年)

我正在尝试在Java中实现一个特殊用途计时器,它针对超时处理进行了优化.例如,用户可以使用死线注册任务,并且计时器可以在死线结束时通知用户的回调方法.在大多数情况下,注册任务将在很短的时间内完成,因此大多数任务将被取消(例如task.cancel())或重新安排到将来(例如task.rescheduleToLater(1,TimeUnit.SECOND)) .

我想使用此计时器来检测空闲套接字连接(例如,在10秒内没有收到消息时关闭连接)和写入超时(例如,当写操作未在30秒内完成时引发异常.)在大多数情况下,超时不会发生,客户端将发送一条消息,除非有一个奇怪的网络问题,否则将发送响应.

我不能使用java.util.Timer或java.util.concurrent.ScheduledThreadPoolExecutor,因为它们假设大多数任务都应该超时.如果取消任务,则取消的任务将存储在其内部堆中,直到调用ScheduledThreadPoolExecutor.purge(),这是一项非常昂贵的操作.(也许是O(NlogN)？)

在我在CS类中学到的传统堆或优先级队列中,更新元素的优先级是一项昂贵的操作(在许多情况下为O(logN),因为它只能通过删除元素并重新插入元素来实现.新的优先级值.像Fibonacci堆的一些堆有减少Key()和min()操作的O(1)时间,但我至少需要快速的raiseKey()和min()(或者reduceKey()和max()) .

您是否知道针对此特定用例高度优化的任何数据结构？我正在考虑的一个策略是将所有任务存储在哈希表中并每隔一秒左右迭代所有任务,但这并不是那么美妙.

Stack Overflow上有一些线程涉及在.Net和C#中实现优先级队列.

我的问题是一个更基本的问题:为什么在.Net框架中没有开箱即用的优先级队列？甚至C++标准库也有一个.

我正在尝试将对存储在优先级队列中,并且我使用比较函数来比较每对的第二个值.

#include<iostream>
#include<queue>
#include<utility>
using namespace std;

class CompareDist
{
public:
    bool operator()(pair<int,int> n1,pair<int,int> n2) {
        return n1.second>n2.second;
    }
};
int main()
{
    priority_queue<pair<int,int>,CompareDist> pq;
}

当我编译这个时,我得到一个错误

error: no type named ‘value_type’ in ‘class CompareDist’

可能是什么原因.我是STL的新手.

我正在阅读CLRS第三版中的 Dijkstra算法(第662页).这是我不明白的书中的一部分:

如果图形足够稀疏 - 特别是E = o(V^2/lg V)- 我们可以通过使用二进制最小堆实现最小优先级队列来改进算法.

图为什么要稀疏？

这是另一部分:

每个DECREASE-KEY操作都需要时间O(log V),并且最多仍然有E这样的操作.

假设我的图形如下所示:

我想计算从1到6的最短路径并使用最小堆方法.首先,我将所有节点添加到最小优先级队列.构建最小堆后,min节点是源节点(因为它与自身的距离为0).我提取它并更新其所有邻居的距离.

然后我需要调用decreaseKey距离最小的节点来创建一个新的最小堆.但是如何在恒定时间内知道它的指数呢？

节点

private static class Node implements Comparable<Node> {

    final int key;
    int distance = Integer.MAX_VALUE;
    Node prev = null;

    public Node(int key) {
        this.key = key;
    }

    @Override
    public int compareTo(Node o) {
        if (distance < o.distance) {
            return -1;
        } else if (distance > o.distance) {
            return 1;
        } else {
            return 0;
        }
    }

    @Override …

可能重复:
C#可排序集合,允许重复键

基本上我想使用重复键使Dictionary工作,而无需进入自定义比较器实现.有一个想法:

  Dictionary<key, List<value>>

但它仍然有一些开销.我希望词典有"AllowDuplicates".

使用我所知道的优先级队列的唯一例子是Dijkstra算法(用于计算最低成本)

在其他情况下它会有用吗？

Java标准库中的Priority Queue实现似乎是最小优先级队列,我发现有些令人困惑.为了将其变为最大值,我创建了一个自定义比较器对象.

Comparator<Integer> cmp = new Comparator<Integer>()
{
    public int compare( Integer x, Integer y )
    {
        return y - x;
    }
};

我想知道是否有更优雅的解决方案.基本上我不是一个可用于实现Dijkstras等的通用优先级队列.我甚至没有意识到会有反向操作的那些:/

优先级队列具有每个条目的优先级值和数据.

因此,在向队列添加新元素时,如果它具有比集合中已有的元素更高的优先级值,则它会向表面冒泡.

当一个人调用pop时,我们获得具有最高优先级的元素的数据.

在Javascript中有效实现这样的优先级队列是什么？

有一个名为PriorityQueue的新对象,创建两个带有两个参数(数据,优先级)的方法(推送和弹出)是否有意义？作为一个编码器,这对我来说是有意义的,但我不确定在下腹部使用哪种数据结构将允许操纵元素的排序.或者我们可以将它们全部存储在一个数组中并每次遍历数组以获取具有最高优先级的元素？

这样做的好方法是什么？