3

所以我在这个 C++ 类中，我似乎不明白如何解决这个问题。

为字符串实现优先级队列。优先级队列类似于常规队列，只是添加到队列中的每个项目也具有关联的优先级。对于这个问题，将优先级设为整数，其中 0 是最高优先级，值越大优先级越低。

remove 函数应该返回并删除具有最高优先级的项目，例如：

q.add("X",10);
q.add("Y",1);
q.add("Z",3);

cout << q.remove(); //returns Y
cout << q.remove(); //returns Z
cout << q.remove(); //returns X

.

这是我到目前为止所拥有的。

http://pastebin.com/AgXL9dfq

基本上，我只需要 add() 和 remove() 函数，我不明白如何实现。有什么帮助吗？提前致谢。

4

2 回答 2

2

这是另一个使用std::map和的解决方案std::vector

#include <iostream>
#include <map>
#include <vector>

class priority_queue {
    std::map<int, std::vector<std::string>> queue;
public:
    void add(int priority, std::string str) {
        if(!queue[priority].empty()) {
            queue[priority].push_back(str);
        } else {
            std::vector<std::string> vec;
            vec.push_back(str);
            queue[priority] = vec;
        }
    }
    std::string remove() {
        if(!queue.begin()->second.empty()) {
            std::string temp = queue.begin()->second[0];
            queue.begin()->second.erase(queue.begin()->second.begin());
            if(queue.begin()->second.empty())
                queue.erase(queue.begin());
            return temp;
        }
        std::cout << "ERROR: QUEUE EMPTY!" << std::endl;
        return "";
    }
};


int main() {
    priority_queue pq;

    pq.add(10, "hello");
    pq.add(10, "world");
    pq.add(11, "how");
    pq.add(12, "are");
    pq.add(13, "you?");

    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
    std::cout << pq.remove() << std::endl;
}

它生成以下输出：

hello
world
how
are
you?

它通过使用具有int表示优先级的键值和std::vector<std::string>作为其值的映射来工作，即具有相同优先级的值的集合。

add()方法检查映射中是否已经存在具有给定优先级的值 - 如果有，它只是将字符串值推到向量的后面，如果没有，它会创建一个新向量，将值推回，并将其分配给map[priority].

remove()方法检查队列是否为空，如果不是，则从值容器向量的前面获取适当的值；如果“弹出”字符串恰好是向量中的最后一个，则意味着不再有与其优先级相关的值，并且整个条目将从映射中删除，以免引起进一步的问题。

于 2013-11-14T20:09:31.677 回答
0

您正在寻找的是堆数据结构。堆是满足以下条件的二叉树：

  • 每个节点都有一个父节点、一个左子节点和一个右子节点（它们可能是NULL）
  • 每个节点都有一个键和一个优先级
  • 如果p是 的父级u，则p.priority<u.priority

了解所有这些，您可以有效地实施insert(key, priority)操作remove()。更具体地说，每个提到的操作的复杂度为O(log N)，其中 N 是优先级队列的大小。有关堆数据结构的更多信息，请参见 Wikipedia：http://en.wikipedia.org/wiki/Heap_(data_structure)。下面我发布了一些我写的代码（我没有对它进行很多测试，但我认为它有效）。

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

#define MAXN 100005
#define L(n) (2*n)
#define R(n) (2*n+1)
#define P(n) (int)(n/2)

struct Node {
  int p;
  string s;
  void swap(Node &other) {
    Node tmp = (Node){p, s};
    p = other.p, s = other.s;
    other.p = tmp.p, other.s = tmp.s;
  }
};

template<typename Key, typename Priority>
struct PriorityQueue {
private:
  vector<pair<Key, Priority> > pq;
  int size;

  void bubble_up(int u) {
    while(P(u)) {
      if(pq[P(u)].second > pq[u].second) {
        swap(pq[u], pq[P(u)]);
        u = P(u);
      } else break;
    }
  }

  void bubble_down(int u) {
    while(L(u) <= size) {
      int pp = min(pq[u].second, pq[L(u)].second);
      if(R(u) <= size) pp = min(pp, pq[R(u)].second);
      if(pp == pq[u].second) break;
      else if(pp == pq[L(u)].second) {
        swap(pq[u], pq[L(u)]);
        u = L(u);
      } else {
        swap(pq[u], pq[R(u)]);
        u = R(u);
      }
    }
  }

public:
  PriorityQueue() : pq(1), size(0) {}

  void add(Key key, Priority priority) {
    pq.push_back(make_pair(key, priority));
    bubble_up(++size);
  }

  Key remove() {
    Key ret = pq[1].first;
    swap(pq[1], pq[size--]);
    pq.pop_back();
    bubble_down(1);
    return ret;
  }
};

int main() {
  PriorityQueue<string, int> Q;

  Q.add("X", 10);
  Q.add("Y", 1);
  Q.add("Z", 3);
  Q.add("K", 7);

  cout << Q.remove() << endl;
  cout << Q.remove() << endl;
  cout << Q.remove() << endl;
  cout << Q.remove() << endl;

  return 0;
}

编辑：我将函数add()和remove()放入一个名为PriorityQueue. 我还扩展了结构以接受其他类型的键和优先级。我希望它有帮助:)

于 2013-11-14T19:49:16.000 回答