12

这不是家庭作业。

我正在使用一个小的“优先队列”（目前实现为数组）来存储具有最小值的最后 N 个项目。这有点慢 - O(N) 项插入时间。当前的实现跟踪数组中最大的项目并丢弃任何不适合数组的项目，但我仍然想进一步减少操作数量。

寻找符合以下要求的优先级队列算法：

  1. 队列可以实现为数组，它具有固定大小并且_不能_增长。严格禁止在任何队列操作期间进行动态内存分配。
  2. 任何不适合数组的东西都会被丢弃，但队列会保留所有遇到过的最小元素。
  3. O(log(N)) 插入时间（即，将元素添加到队列中应该占用 O(log(N))）。
  4. （可选）O(1) 访问队列中*最大* 的项目（队列存储 *最小* 项目，因此最大的项目将首先被丢弃，我需要它们来减少操作次数）
  5. 易于实施/理解。理想情况下——类似于二分搜索——一旦你理解了它，你就会永远记住它。
  6. 元素不需要以任何方式排序。我只需要保持 N 曾经遇到过的最小值。当我需要它们时，我会立即访问所有这些。所以从技术上讲，它不必是一个队列，我只需要存储 N 个最后的最小值。

我最初考虑使用二进制堆（它们可以通过数组轻松实现），但显然当数组不能再增长时它们表现不佳。链表和数组需要额外的时间来移动东西。stl 优先级队列增长并使用动态分配（不过我可能错了）。

那么，还有其他想法吗？

--EDIT--
我对 STL 的实现不感兴趣。由于大量的函数调用，STL 实现（由少数人建议）的工作速度比当前使用的线性数组慢一些。

我对优先队列算法感兴趣，而不是实现。

4

8 回答 8

18

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

您使用最大堆。

假设您有一个 N 元素堆（实现为数组），其中包含迄今为止看到的 N 个最小元素。

当一个元素进入时，您检查最大（O（1）时间），如果它更大，则拒绝。

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

筛选过程很简单：从 root 开始，在每个步骤中，您都将这个值与它的较大的孩子交换，直到恢复 max-heap 属性。

因此，如果您使用 std::priority_queue ，您将不必执行任何可能必须执行的删除操作。根据 std::priority_queue 的实现，这可能会导致内存分配/释放。

所以你可以有如下代码：

  • 大小为 N 的已分配数组。
  • 用你看到的前 N ​​个元素填充它。
  • heapify（你应该在标准教科书中找到这个，它使用 sift-down）。这是 O(N)。
  • 现在你得到的任何新元素，要么在 O(1) 时间内拒绝它，要么在最坏的情况下通过筛选插入 O(logN) 时间。

但是，平均而言，您可能不必一直筛选新值，并且可能会比 O(logn) 平均插入时间更好（尽管我没有尝试证明它）。

您只分配一次大小为 N 的数组，并且任何插入都是通过交换数组的元素来完成的，因此之后没有动态内存分配。

查看具有 heapify 和 sift-down 伪代码的 wiki 页面：http ://en.wikipedia.org/wiki/Heapsort

于 2010-05-29T17:35:06.213 回答
8

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

旁注：标准容器只有在你让它们增长时才会增长。只要您在插入新项目之前删除一个项目（当然，在它达到其最大大小之后），就不会发生这种情况。

于 2010-05-29T05:15:42.887 回答
1

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

然后添加和删除就像（您的 API 可能会有所不同）......

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

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

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

希望这可以帮助。

于 2010-05-29T11:45:47.343 回答
0

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

于 2010-05-29T05:48:31.043 回答
0

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

于 2010-05-29T06:45:46.120 回答
0

Matters Computational请参阅第 158 页。实现本身非常好，您甚至可以对其稍作调整而不会降低其可读性。例如，当您计算左孩子时：

int left = i / 2;

您可以像这样计算右孩子：

int right = left + 1;
于 2010-05-29T17:38:37.777 回答
0

找到了解决方案（“差异”在代码中表示“优先级”，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. 构建基于最大值的队列（根是最大的）
  2. 直到满，正常加满
  3. 当它满了，对于每一个新元素
    1. 检查新元素是否小于根。
    2. 如果它大于或等于根，则拒绝。
    3. 否则，将 root 替换为新元素并执行正常的堆“筛选”。

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

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

PS 显然，没有足够睡眠的编程不是一个好主意。

于 2010-05-29T18:46:10.030 回答
0

最好使用 std::array 和堆算法来实现自己的类。

  `template<class T, int fixed_size = 5>
   class fixed_size_arr_pqueue_v2
   {
     std::array<T, fixed_size> _data;
     int _size = 0;

     int parent(int i)
     {
       return (i - 1)/2;
     }

     void heapify(int i, bool downward = false)
     {
       int l = 2*i + 1;
       int r = 2*i + 2;
       int largest = 0;
       if (l < size() && _data[l] > _data[i])
        largest = l;
       else
        largest = i;

       if (r < size() && _data[r] > _data[largest])
        largest = r;   

       if (largest != i)
       {
         std::swap(_data[largest], _data[i]);
         if (!downward)
           heapify(parent(i));
         else
           heapify(largest, true);
       }
    }

    public:

    void push(T &d)
    {
       if (_size == fixed_size)
       {
          //min elements in a max heap lies at leaves only. 
          auto minItr = std::min_element(begin(_data) + _size/2, end(_data));
          auto minPos {minItr - _data.begin()};
          auto min { *minItr};

          if (d > min)
          {
             _data.at(minPos) = d;
             if (_data[parent(minPos)] > d)
             { 
                //this is unlikely to happen in our case? as this position is  a leaf?
                heapify(minPos, true);
             }  
             else
                heapify(parent(minPos));
           }           

          return ;
       }

       _data.at(_size++) = d;
       std::push_heap(_data.begin(), _data.begin() + _size);
    }

    T pop()
    {
       T d = _data.front();
       std::pop_heap(_data.begin(), _data.begin() + _size);
       _size--;
       return d;
    }

    T top()
    {
       return _data.front();
    }

    int size() const
    {
       return _size;
    }
 };`
于 2020-03-21T07:37:51.810 回答