c - C语言中如何实现优先级队列？

Question

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

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

比方说，我们有以下场景。 (注意:我认为，更高的值(value)对应更高的优先级):

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

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