二重リンクリストを使用した優先キュー


難易度 ミディアム
よく聞かれる Amazon (アマゾン) 要塞 MAQ ウッカー
リンクリスト 優先キュー キュー

問題文

「二重リンクリストを使用した優先キュー」の問題は、二重リンクリストを使用した優先キューの次の機能を実装するように要求します。 リンクリスト.

  1. push(x、p) :優先度pの要素xを、適切な位置の優先度キューに入れます。
  2. ポップ() :優先度キューで最も優先度の高い要素を削除して返します。
  3. ピーク() :優先度キューで最も優先度の高い要素を削除せずに返します。

push(5, 2)
push(1, 3)
peek()
push(7, 5)
push(9, 1)
pop()
pop()
peek()
1
7
1
5

二重リンクリストを使用して優先キューを実装するアルゴリズム

優先キュー 二重リンクリストの使用は、単一リンクリストを使用する優先キューと同じ方法で実装されます。 ここで二重にリンクされたリストでは、挿入および削除中にいくつかの追加のポインターを変更する必要があります。
二重リンクリストを優先度の高い順に維持し、最も優先度の高い要素が常に最前面にくるようにするという考え方も同じです。

push(x、p)

優先度pの要素xを優先度キューにプッシュするには、要素の適切な場所を見つけて挿入します。 適切な場所は、優先度がp未満の最初の要素の直前です。

たとえば、
priorityQueue =(7、5)->(9、4)->(8、2)
プッシュ(6、3)
(6、3)の適切な場所は、(8、2)の直前、挿入後のキューは、
priorityQueue =(7、5)->(9、4)->(6、3)->(8、2)
明確にするために下の画像を参照してください。

二重リンクリストを使用した優先キュー

  1. トラバース 優先キュー 頭から始めて、優先度がp未満の最初のノードを見つけます。
  2. XNUMXつのケースのうちのXNUMXつが可能です。
  3. 優先度がp未満の要素はありません。 このような場合、優先キューの最後に新しいノードを挿入します。
  4. すべてのノードの優先度はp未満です。 このような場合、優先キューの先頭に新しいノードを挿入します。
  5. 優先度がp未満のノードと、優先度がpより大きいノードがあります。 このような場合、優先度がp未満の最初のノードの前に新しいノードを挿入します。 このケースは上の画像に示されています。

時間の複雑さ = O(N)
スペースの複雑さ = O(1)
ここで、nは、挿入前の優先キュー内のノードの総数です。

ポップ()

最も優先度の高い要素は、優先度キューの先頭にあります。 優先キューが空でない場合は、最初の要素を削除して返します。空でない場合は、ポップできません。

時間計算量= O(1)

ピーク()

最も優先度の高い要素は、優先度キューの先頭にあります。 優先キューが空でない場合は、優先キューの最初の要素の値を返します。

時間計算量= O(1)

コード

二重リンクリストを使用して優先キューを実装するJavaコード

class PriorityQueueUsingDoublyLinkedList {
    // class representing node of a doubly linked list
    static class Node {
        int data;
        int priority;
        Node next, prev;

        public Node(int data, int priority) {
            this.data = data;
            this.priority = priority;
        }
    }

    // head of doubly linked list
    private static Node head = null;

    private static void push(int data, int priority) {
        // if head is null this is the first node to be inserted
        // mark head as new Node
        if (head == null) {
            Node newNode = new Node(data, priority);
            head = newNode;
            return;
        }

        // create a new node with specified data
        Node node = new Node(data, priority);
        // find the first node having priority less than 'priority'
        Node temp = head, parent = null;
        while (temp != null && temp.priority >= priority) {
            parent = temp;
            temp = temp.next;
        }

        // Case 1 : All the nodes are having priorities less than 'priority'
        if (parent == null) {
            // insert the new node at the beginning of linked list
            node.next = head;
            head.prev = node;
            head = node;
        }
        // Case 2 : All the nodes are having priorities greater than 'priority'
        else if (temp == null) {
            // insert the node at the end of the linked list
            parent.next = node;
            node.prev = parent;
        }
        // Case 3 : Some nodes have priority higher than 'priority' and
        // some have priority lower than 'priority'
        else {
            // insert the new node before the first node having priority
            // less than 'priority'
            parent.next = node;
            node.prev = parent;
            node.next = temp;
            temp.prev = node;
        }
    }

    private static int peek() {
        // if head is not null, return the element at first position
        if (head != null) {
            return head.data;
        }
        return -1;
    }

    private static int pop() {
        // if head is not null, delete the element at first position and return its value
        if (head != null) {
            int curr = head.data;
            head = head.next;
            if (head != null) {
                head.prev = null;
            }
            return curr;
        }
        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 node of a doubly linked list
class Node {
    public:
    int data, priority;
    Node *next;
    Node *prev;
    
    Node(int d, int p) {
        data = d;
        priority = p;
        next = prev = NULL;
    }
};

// head of doubly linked list
Node *head = NULL;

void push(int data, int priority) {
    // if head is null this is the first node to be inserted
    // mark head as new Node
    if (head == NULL) {
        Node *newNode = new Node(data, priority);
        head = newNode;
        return;
    }
    
    // create a new node with specified data
    Node *node = new Node(data, priority);
    // find the first node having priority less than 'priority'
    Node *temp = head;
    Node *parent = NULL;
    while (temp != NULL && temp->priority >= priority) {
        parent = temp;
        temp = temp->next;
    }
    
    // Case 1 : All the nodes are having priorities less than 'priority'
    if (parent == NULL) {
        // insert the new node at the beginning of linked list
        node->next = head;
        head->prev = node;
        head = node;
    }
    // Case 2 : All the nodes are having priorities greater than 'priority'
    else if (temp == NULL) {
        // insert the node at the end of the linked list
        parent->next = node;
        node -> prev = parent;
    }
    // Case 3 : Some nodes have priority higher than 'priority' and
    // some have priority lower than 'priority'
    else {
        // insert the new node before the first node having priority
        // less than 'priority'
        parent->next = node;
        node->prev = parent;
        node->next = temp;
        temp->prev = node;
    }
}

int peek() {
    // if head is not null, return the element at first position
    if (head != NULL) {
        return head->data;
    }
    return -1;
}

int pop() {
    // if head is not null, delete the element at first position and return its value
    if (head != NULL) {
        int curr = head->data;
        head = head->next;
        if (head != NULL) {
            head->prev = NULL;
        }
        return curr;
    }
    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