寻找最优的就地排序算法

Question

我在一个航空电子操作系统(线程层)上工作，我正在寻找关于以下(简化)要求的最佳解决方案：“等待各种对象的线程按优先级顺序排队。对于相同的优先级，线程也按FIFO顺序排队”。

例如，各种对象都是信号量。

我认为我可以使用经典的链表来构建这样的等待列表，这使得插入/排序相对快速和容易，并且完全符合预期的使用(一次一个线程进入等待状态)。但是我在一个裸机目标上工作，并且我没有任何libc支持，因此我没有malloc (这对于链表非常有用！)

为了按照优先级对线程进行排序，我通常使用二进制堆(http://en.wikipedia.org/wiki/Binary_heap)，它非常高效，但在这里不能使用它，因为“先进先出顺序”不能以这种方式管理。

当然，我可以使用更经典的排序算法，但它们通常很耗时，甚至对于一次插入也是如此，因为每次插入时可能会移动许多数组元素。

所以我想知道是否有合适的算法存在。也许是一种改进的二进制堆？还是“静态”链表？或者也许最好的事情是与链表相关联的分配器算法？

关于信息：-线程的总数被限制在128，所以内存需求总是有限的，并且可以在编译时知道/保留。-我有一个有限的数量或内存，所以我几乎不能做这样的二进制堆的构造，按FIFO上的优先级排序(自然按到达时间排序)…

我真的很感激任何关于这个问题的想法和新鲜的看法。

谢谢！

Answer 1

您可能需要一个稳定的就地排序-它将在按优先级排序后保持项目的相对顺序，满足您的FIFO要求。

从维基的列表中挑选任何东西，例如就地合并排序，块排序和tim排序都是就地和稳定的：http://en.wikipedia.org/wiki/Sorting_algorithm

关于内存分配和链表--也许你可以实现你自己的malloc？您可以分配固定大小的堆(128 *线程信息大小)，然后使用每个块的索引作为指针。因此，对象的实际指针将是(堆起始地址)+ index *(块大小)。然后像往常一样实现排序，但使用索引而不是指针。

另一个想法是将FIFO要求与优先级队列要求分开，并使用相同优先级项目的队列对容器进行排序-但这将需要动态列表分配和更大的堆。

Answer 2

解决这个问题的标准技术是Bentley-Saxe优先级队列。我将在这里详细描述它，以及如何以最小的内存需求就地实现它的一些技巧，但我所说的任何事情都只是重申Pat Morin在CS理论StackExchange上的出色答案：Pat Morin's answer to "Is there a stable heap?" on cstheory.SE