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

Question

我需要使用单链表在 C 编程中实现优先级队列。

我对优先队列没有明确的概念。我用谷歌搜索，但没有完全理解我发现了什么。我的理解是优先级队列是一个元素按优先级排序的队列。列表中的插入根据元素优先级定位在列表中。

可以说，我们有以下场景。（注意：我认为，更高的价值具有更高的优先级）：

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

如果需要插入另一个元素，请说明Element-->3 (priority=3)哪个具有更高的优先级。

我可以移动前一个元素 ，Element-->2 (priority=2)然后Element-->3 (priority=3)在位置 0插入这个新元素，并Element-->2 (priority=2)移动到列表中的位置 1。

现在名单变成了，

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

同样，在插入的基础上，我是否必须将列表中的所有元素都移动？

这样对吗？

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

如果您的列表有指向末尾的指针，您也可以为低于末尾的优先级添加特殊检查。