使用单链接列表的优先级队列


难度级别 中等
经常问 BrowserStack 葫芦 马恒达康维瓦 口袋宝石 索罗科
链表 队列

优先 队列 单独使用 链表 问题,我们需要通过使用单链接列表来实现优先级队列。 优先级队列包含以下操作,

  1. push(x,p):在优先级队列的适当位置添加优先级为p的元素x。
  2. pop():删除并返回优先级最高的元素
  3. peek():返回优先级最高的元素

使用案列

输入:
推(5,2)
推(1,3)
窥视()
推(7,5)
推(9,1)
流行音乐()
流行音乐()
窥视()
输出:
1
7
1
5

单链表的优先队列算法

这个想法是要按照优先级从高到低的顺序维护链表,以便将最高优先级的元素放在最前面。

推(x,p)

由于元素按优先级从高到低的顺序排列,因此优先级为p的元素插入优先级小于p的第一个元素之前,因此不会干扰优先级的顺序。 出现三种情况

  1. 没有优先级小于p的元素,请在链接列表的末尾添加新元素。
  2. 所有元素的优先级均小于p,请在链接列表的开头添加新元素。
  3. 一些元素的优先级小于p,而其他元素的优先级大于p,请在第一个元素的优先级小于p之前添加新元素。

使用单链接列表的优先级队列

时间复杂度= O(N)

使用单链表的优先级队列的伪代码

  1. 创建一个新节点,其data = x且priority = p,将其设为newNode
  2. 如果head为null,则这是要插入的第一个节点,因此使head = newNode并返回。
  3. 创建一个节点temp等于head和一个节点prev等于null。
  4. 通过在temp不为null且temp的优先级大于p的情况下运行循环,找到优先级小于p的第一个节点。 在每次迭代时,将prev更新为temp,将temp更新为temp.next。
  5. 循环结束后,如果temp为null,则意味着没有优先级小于p的节点,将newNode插入链表的末尾,即执行prev.next = newNode。
  6. 否则,如果prev为null,则意味着所有节点的优先级都大于p。 做newNode.next = head和head = newNode。
  7. 否则,在temp之前插入新节点,即执行newNode.next = temp和prev.next = newNode。

流行音乐()

链接列表的最前面包含优先级最高的元素,将其删除然后返回。

时间复杂度= O(1)

窥视()

链接列表的最前面包含优先级最高的元素,请返回该元素。

时间复杂度= O(1)

使用单链接列表的优先级队列的JAVA代码

public class PriorityQueueUsingSinglyLinkedList {
    // class representing node of a linked list
    static class Node {
        int data;
        int priority;
        Node next;
        
        public Node(int data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }

    // Variable representing the head of linked list
    private static Node head = null;

    private static void push(int x, int p) {
        // Create a new node
        Node newNode = new Node(x, p);

        // If head is null, this is the first node to be added
        // so make head = newNode
        if (head == null) {
            head = newNode;
            return;
        }

        Node temp = head;
        Node prev = null;

        // search for first node having priority less than p
        while (temp != null && temp.priority > p) {
            prev = temp;
            temp = temp.next;
        }

        if (temp == null) {
            // no node with priority less than this node (Case 1)
            prev.next = newNode;
        } else {
            if (prev == null) {
                // all the nodes have priority less than p (Case 2)
                // add this node at the starting
                newNode.next = head;
                head = newNode;
            } else {
                // Case 3
                // add this node before the node with priority less than p 
                newNode.next = temp;
                prev.next = newNode;
            }
        }
    }

    private static int peek() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            return head.data;
        }
        return -1;
    }

    private static int pop() {
        // head of the linked list contains the maximum priority element
        if (head != null) {
            int data = head.data;
            // removing the highest priority element
            head = head.next;
            return data;
        }
        return -1;
    }

    public static void main(String[] args) {
        // Example
        push(5, 2);
        push(1, 3);
        System.out.println(peek());
        push(7, 5);
        push(9, 1);
        System.out.println(pop());
        System.out.println(pop());
        System.out.println(peek());
    }
}
1
7
1
5

使用单链接列表的优先级队列的C ++代码

#include<bits/stdc++.h> 
using namespace std;

// class representing a tree node
class Node {
    public:
    int data;
    int priority;
    Node *next;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = NULL;
    }
};

// function to create a new node
Node* newNode(int x, int p) {
    Node *node = new Node(x, p);
    return node;
}

// Variable representing the head of linked list
Node *head = NULL;

void push(int x, int p) {
    // Create a new node
    Node *node = newNode(x, p);
    
    // If head is null, this is the first node to be added
    // so make head = newNode
    if (head == NULL) {
        head = node;
        return;
    }
    
    Node *temp = head;
    Node *prev = NULL;
    
    // search for first node having priority less than p
    while (temp != NULL && temp->priority > p) {
        prev = temp;
        temp = temp->next;
    }
    
    if (temp == NULL) {
        // no node with priority less than this node (Case 1)
        prev->next = node;
    } else {
        if (prev == NULL) {
            // all the nodes have priority less than p (Case 2)
            // add this node at the starting
            node->next = head;
            head = node;
        } else {
            // Case 3
            // add this node before the node with priority less than p
            node->next = temp;
            prev->next = node;
        }
    }
}

int pop() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        int data = head->data;
        // removing the highest priority element
        head = head->next;
        return data;
    }
    return -1;
}

int peek() {
    // head of the linked list contains the maximum priority element
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int main() {
    // Example
    push(5, 2);
    push(1, 3);
    cout<<peek()<<endl;
    push(7, 5);
    push(9, 1);
    cout<<pop()<<endl;
    cout<<pop()<<endl;
    cout<<peek()<<endl;
    
    return 0;
}
1
7
1
5

编号1    参考2