空间有限的优先级队列:寻找一个好的算法

基于数组的堆似乎非常适合您的目的。我不知道你为什么拒绝他们。

使用max堆。

假设您有一个n元素堆(作为数组实现),其中包含迄今为止看到的n个最小元素。

当一个元素进入时,您将对照max(o(1)次)进行检查,如果它更大,则拒绝。

如果输入的值较低,则将根修改为新值,并筛选此更改的值-最坏情况下的O(log n)时间。

筛选过程很简单:从根目录开始,在每个步骤中,您都将这个值与它较大的子目录交换,直到恢复max heap属性。

所以,你不必做任何事 删除 如果您使用std::priority_queue,那么您可能必须这样做。根据std::priority_队列的实现,这可能导致内存分配/释放。

因此,代码如下:

• 分配的数组大小为n。
• 用您看到的前n个元素填充它。
• 堆积(你应该在标准的课本中找到它,它使用筛选)。这是O(n)。
• 现在您得到的任何新元素,要么在O(1)时间内拒绝它,要么在最坏的情况下通过筛选O(logn)时间来插入。

不过,平均而言,您可能不必一直筛选新值,而且可能会比O(logn)平均插入时间更好(尽管我没有尝试证明这一点)。

只分配一次大小n数组,任何插入都是通过交换数组的元素来完成的,因此之后就没有动态内存分配了。

查看wiki页面,该页面包含用于堆积和筛选的伪代码: http://en.wikipedia.org/wiki/Heapsort

使用 std::priority_queue 与 最大的 头部的物品。对于每个新项目,如果是,则丢弃它 >= 头项,否则弹出头项并插入新项。

旁注:标准容器只有在您使其增长时才会增长。只要在插入新项目之前删除一个项目(当然,在达到最大大小之后),就不会发生这种情况。

我工作的大多数优先级队列都基于链接列表。如果您有预先确定的优先级数量,那么您可以通过拥有一个链表数组(每个优先级一个链表)轻松地创建一个插入o(1)的优先级队列。具有相同优先级的项目当然会退化为FIFO,但这可以被认为是可接受的。

添加和删除之后会变得类似(您的API可能会有所不同)。

listItemAdd (&list[priLevel], &item);      /* Add to tail */
pItem = listItemRemove (&list[priLevel]);  /* Remove from head */

然后,获取队列中的第一个项目将成为查找具有最高优先级的非空链接列表的问题。这可能是O(N),但有几个技巧可以用来加快速度。

1. 在优先级队列结构中,保持指向链接列表的指针或索引或其他具有当前最高优先级的内容。每次从优先级队列中添加或删除项目时,都需要更新此项。
2. 使用位图指示哪些链接列表不是空的。结合查找最高有效位或查找最低有效位算法,您通常可以一次测试多达32个列表。同样,这需要在每次添加/删除时更新。

希望这有帮助。

如果优先级的数量很小且固定,则可以为每个优先级使用环形缓冲区。如果对象很大,这将导致空间浪费,但是如果它们的大小与指针/索引相当,那么在对象中存储额外指针的变量可能以同样的方式增加数组的大小。
也可以在数组中使用简单的单链表,存储2*m+1个指针/索引,其中一个指向第一个空闲节点,其他对指向每个优先级的头和尾。在这种情况下,在用O(1)取出下一个节点之前,必须比较平均O(M)。插入需要O(1)。

如果以最大大小构造STL优先级队列(可能来自用占位符初始化的向量),然后在插入之前检查大小(如有必要,请事先删除一个项),则在插入操作期间将永远不会有动态分配。STL实现非常有效。

Matters Computational 请参阅第158页。实现本身非常好,您甚至可以在不降低可读性的情况下稍微调整它。例如,当您计算左子项时,如下所示:

int left = i / 2;

你可以这样计算右子:

int right = left + 1;

找到一个解决方案(“difference”在代码中表示“priority”,maxrememberedresults为255(可以是任意(2^n-1)):

template <typename T> inline void swap(T& a, T& b){
    T c = a;
    a = b;
    b = c;
}


struct MinDifferenceArray{
    enum{maxSize = maxRememberedResults};
    int size;
    DifferenceData data[maxSize];
    void add(const DifferenceData& val){
        if (size >= maxSize){
            if(data[0].difference <= val.difference)
                return;

            data[0] = val;

            for (int i = 0; (2*i+1) < maxSize; ){
                int next = 2*i + 1;
                if (data[next].difference < data[next+1].difference)
                    next++;
                if (data[i].difference < data[next].difference)
                    swap(data[i], data[next]);
                else
                    break;
                i = next;
            }
        }
        else{
            data[size++] = val;
            for (int i = size - 1; i > 0;){
                int parent = (i-1)/2;
                if (data[parent].difference < data[i].difference){
                    swap(data[parent], data[i]);
                    i = parent;
                }
                else
                    break;
            }
        }
    }

    void clear(){
        size = 0;
    }

    MinDifferenceArray()
        :size(0){
    }
};

1. 生成基于max的队列(根最大)
2. 直到加满,正常加满
3. 当它满了,为每一个新元素
   1. 检查新元素是否小于根。
   2. 如果大于或等于根,则拒绝。
   3. 否则,用新元素替换根,并执行正常的堆“筛选”。

我们得到O(log(n))插入作为最坏的情况。

它与用户提供的昵称为“白痴”的解决方案相同。 谢谢大家的回复。

显然,在没有足够睡眠的情况下编程不是一个好主意。