我有以下排序场景：
给定一个包含未排序数据的输入数组：1、5、2、6、9
a) 按降序排列，即 9、6、5、2、1
b) 将当前排序列表的最大值 9 发送到输出
c) 修改一些其余的值，即5变成10，1变成3
d) 将排序列表的其余部分更新为 10、6、3、2
e) 从 b) 重复直到所有未访问的值都发送到输出（这些值可能在每次发送后更新）
有谁知道什么样的应用程序或特定问题可以使用这种情况？最好的算法是使用两个链表来交换索引而不是插入和删除大量更新的数据吗？谢谢
问问题
49 次
3 回答
2
这听起来像是某种优先级队列。给定时间的最高优先级得到处理，从而从队列中删除。其他元素可能会获得优先级更改，因此在队列中前后移动。
假设列表很大（因此甚至值得考虑性能）并且更新元素的数量与元素总数相比相当小，我建议使用快速排序，所有未更改的元素都被视为已排序和已更改按算法规定插入的元素。
如果元素的大小相关，而不仅仅是数字，则独立于算法，您可能想要对它们的引用或指针进行排序，而不是实际元素。
于 2013-03-20T14:05:35.093 回答
0
What you are looking for is called Heap (http://en.wikipedia.org/wiki/Heap_(data_structure)), which has its implementation in C++/STL as priority_queue and also there are functions push_heap, pop_heap (http://www.cplusplus.com/reference/algorithm/push_heap/) which work on array.
When using heap complexity of insertion/deletion/update is O(logN), and getting maximum element is O(1) so it fits best to your needs.
于 2013-03-20T14:16:58.327 回答
0
您可以将优先级队列与其他操作一起使用：密钥修改。它可以用于Dijkstra 算法的实现。例如，在 Robert Sedgewick 的书“C++/C/Java 中的算法”中描述了这种具有底层二进制堆的数据结构
于 2013-03-20T14:04:52.020 回答