使用單鏈接列表的優先級隊列


難度級別
經常問 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