如何在C编程中实现优先队列？

Question

我需要用单向链表在C编程中实现一个优先队列。

我对优先队列没有清晰的概念。我搜索了一下，但是并没有完全理解我找到的东西。我的理解是，优先队列是一个按照优先级排序元素的队列。插入列表的位置取决于元素的优先级。

假设我们有以下情景。（注意：我假设较高的值具有较高的优先级）：

Element-->2 (priority=2)  (Now in position 0)

如果需要插入另一个元素，比如 Element-->3 (priority=3)，它的优先级更高，则可以将前一个元素Element-->2 (priority=2)移动，在列表中的位置0插入这个新的Element-->3 (priority=3)，并将Element-->2 (priority=2)移动到列表中的位置1。

现在列表变成了：

Element-->3 (priority=3) followed by Element-->2 (priority=2)

同样地，基于插入操作，我是否需要将列表中的所有元素都进行移动？

这样正确吗？

- Dinesh

---

到目前为止还不错——你的实现遇到了问题吗？ - sarnold

简单来说，当需要在列表上进行操作时，它会选择具有最高优先级的项目进行操作...如何实现这一点取决于您是将最高优先级元素放在列表前面还是放在堆前面（如果使用堆）。 - nikel

Answer 1

您无需“移动”列表，而是在插入时执行以下操作（伪代码）：

if new_node.priority > list.head.priority:
    new_node.next = list.head
    list.head = new_node
else:
    previous = null
    for current = list.head:
        if current.priority < node.priority:
            previous.next = node
            node.next = current
            break loop
        previous = current

如果您的列表有指向结尾的指针，您可以添加一个特殊的检查，以便优先级低于结尾的元素也可以被添加。

- Some programmer dude

Answer 2

我认为你遇到了麻烦，因为优先队列应该使用堆树来实现，而不是使用单向链表。

堆使所有操作变得容易--在堆中，更新、删除和插入的所有操作都非常便宜：O(log n)。

- Anthony Blake

Answer 3

你已经熟悉了优先队列。但是……

链表不同于简单的数组。

链表中每个元素都有一个指向下一个元素的引用。只需改变这两个元素的引用，就可以在另一个元素后面插入一个元素。

+--------+
| item A |                           +--------+
+--------+     +--------+            | item C |
|ref to B|---->| item B |            +--------+
+--------+     +--------+            |  NULL  |
               |  NULL  |            +--------+
               +--------+

在A和B之间插入C的方法如下：

1. 通过将C中的NULL更改为ref to B
2. 通过将A中的ref to B更改为ref to C

- mouviciel

Answer 4

好的，我不知道为什么你需要用C语言。在C++ STL中它是可用的。

但既然你想要，这里是你所需代码的源链接。

http://matrixsust.blogspot.com/2011/11/basic-priority-queue-in-c.html

或者

http://www.indiastudychannel.com/projects/4870-Priority-queue-using-array.aspx

希望它能帮到你。

- Robel Sharma

---

第二个链接指向明显无效的C代码。至少“initpque”将一些内容写入了以前未分配的指针中。不仅如此，在算法方面实现也是错误的：加法是O(n²)! - Nikita Kipriyanov

Answer 5

优先队列是一种抽象数据类型，基本上按照某个选择的关键字（升序或降序）对其中的项目进行排序。正如安东尼·布雷克所提到的那样，堆实现是最直接的方法，您使用的底层结构只是一个数组，并且您执行一些以数组索引为中心的操作。

如果出于某种原因您想要使用单向链表来实现，下面是一段演示代码，以就地方式执行排序插入：

void sortedInsert(struct node **headRef,int data){
struct node *newnode=(struct node *)malloc(sizeof(struct node));
assert(newnode);
newnode->value=data;
newnode->next=NULL;

if(!(*headRef) || data<(*headRef)->value){
    newnode->next=*headRef;
    *headRef=newnode;
}else{
    struct node *prev=*headRef;

    while(prev->next && prev->next->value<data)
        prev=prev->next;

    struct node *temp=prev->next;
    prev->next=newnode;
    newnode->next=temp;
}

}

- Moses Xu