列表到优先级队列 [英] List to priority queue

问题描述

我在C ++中有一个大学编程项目，分为两部分。我求第二部分应该使用 priority_queues ，散列表和 BST 。

我遇到了问题（至少）与优先级队列，因为它强制自己重做了很多代码已经实现在第一

该项目是关于实施简单机场管理系统的项目，因此，我有类似机场（主班），飞机，航站楼和航班。我的机场有一个列表的终端，但现在项目规范指出，我必须保持终端 priority_queue 其中顶部包含终端少占用，即具有较少的航班。

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

我该怎么办？ p>

提前感谢。

解决方案

有效提高和降低关键操作。您可能更适合创建自己的优先级队列实现。

priority_queue容器适用于动态集合。但由于机场终端的数量几乎固定，你可以一个固定大小的容器与堆的算法家庭。

作为内部存储，你可以使用任何容器提供随机访问迭代器（向量，数组，deque）。然后，使用make_heap（），sort_heap（）函数来堆积数组。现在你可以低价访问top（），修改堆中随机成员的优先级，并轻松遍历所有元素。

例如：
http://www.cplusplus.com/reference/algorithm/make_heap/

I have a college programming project in C++ divided into two parts. I beggining the second part where it's supposed to use priority_queues, hash tables and BST's.

I'm having trouble (at least) with priority queues since it's obligating myself to redone a lot of code already implemented in the first part.

The project it's about implementing a simple airport management system and, therefore, I have classes like Airport (main class), Airplane, Terminal and Flight. My airport had a list of terminals but now the project specification points out that I must keep the terminals in a priority_queue where the top contains the terminal less occupied, i.e has less flights.

For each class, I have CRUD functions but now how am I supposed, for example, edit a terminal and add a flight to it? With a list, I just had to iterate to a specific position but now I only have access to object in the top of the queue. The solution I thought about was to copy the priority queue terminals to a temporary list but, honestly, I don't like this approach.

What should I do?

Thanks in advance.

解决方案

It sounds like you need a priority queue with efficient increase and decrease key operations. You might be better of creating you own your own priority queue implementation.

The priority_queue container is great for dynamic sets. But since the number of terminal in an airport are pretty much fixed you can a fixed size container with the heap family of algorithms.

As the internal storage, you could use any container that provides random access iterators (vector, array, deque). Then, use make_heap(), sort_heap() family of functions to heapify the array. Now you can cheaply access the top(), modify the priority of a random member in the heap and iterate through all elements easily.

For an example see: http://www.cplusplus.com/reference/algorithm/make_heap/

这篇关于列表到优先级队列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！