c++ - 列表到优先队列

Question

我有一个 C++ 大学编程项目，分为两部分。我开始第二部分，它应该使用 priority_queues、hash tables 和 BST。

我(至少)在优先级队列方面遇到了麻烦，因为它迫使我自己重做第一部分中已经实现的大量代码。

该项目是关于实现一个简单的机场管理系统，因此，我有 Airport(主类)、Airplane、Terminal 和 Flight 等类。我的机场有一个 list 航站楼，但现在项目规范指出我必须将航站楼放在 priority_queue 中，顶部包含航站楼占用较少，即航类较少。

对于每个类，我都有 CRUD 函数，但现在我应该如何编辑航站楼并向其添加航类？有了列表，我只需要迭代到特定位置，但现在我只能访问队列顶部的对象。我想到的解决方案是将优先队列终端复制到一个临时列表，但老实说，我不喜欢这种方法。

我该怎么办？

提前致谢。

Answer 1

听起来您需要一个具有高效增减键操作的优先级队列。您最好创建自己的优先级队列实现。

priority_queue 容器非常适合动态集。但是由于机场中的航站楼数量几乎是固定的，因此您可以使用堆系列算法来固定大小的容器。

作为内部存储，您可以使用任何提供随机访问迭代器( vector 、数组、双端队列)的容器。然后，使用 make_heap(), sort_heap() 系列函数对数组进行堆化。现在您可以廉价地访问 top()，修改堆中随机成员的优先级并轻松地遍历所有元素。

例子见: http://www.cplusplus.com/reference/algorithm/make_heap/