နှစ်ထပ်ဆက်ထားသောစာရင်းကို အသုံးပြု၍ ဦး စားပေးတန်းစီသည်


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Citadel MAQ Wooker
ချိတ်ဆက်စာရင်း ဦး စားပေးတန်းစီ ဆံပင်ကြိုး

ပြProbleနာဖော်ပြချက်

ပြdoubနာက“ Priority Queue ကိုနှစ်ဆဆက်တိုက်ဆက်နွယ်နေသောစာရင်းကိုအသုံးပြုခြင်း” သည်အောက်ပါ ဦး စားပေးတန်းစီ၏လုပ်ဆောင်ချက်များကိုနှစ်ဆအသုံးပြုရန်တောင်းဆိုသည် ဆက်စပ်စာရင်း.

  1. တွန်းအားပေး (x, p) : သင့်လျော်သောအနေအထားမှာ ဦး စားပေးတန်းစီအတွက် ဦး စားပေး p နှင့်အတူ element တစ်ခု x ကို enqueue ။
  2. ပေါ့ပ် () : ဦး စားပေးတန်းစီအတွက်အမြင့်ဆုံး ဦး စားပေးနှင့်အတူ element ကိုဖယ်ရှားခြင်းနှင့်ပြန်လာ။
  3. peek () : ၎င်းကိုဖယ်ရှားခြင်းမပြုဘဲ၊ ဦး စားပေးတန်းစီတွင်အမြင့်ဆုံး ဦး စားပေးသည့် element ကိုပြန်ပို့ပါ။

နမူနာ

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

နှစ်ထပ်ချိတ်ထားသောစာရင်းကို အသုံးပြု၍ Priority Queue ကိုအကောင်အထည်ဖော်ရန် Algorithm က

ဦး စားပေးတန်းစီ နှစ်ထပ်ကွမ်းချိတ်ဆက်ထားသောစာရင်းကိုအသုံးပြုခြင်းကိုတစ်မျိုးတည်းသောချိတ်ဆက်ထားသောစာရင်းကို အသုံးပြု၍ ဦး စားပေးတန်းစီကဲ့သို့တူညီစွာအကောင်အထည်ဖော်သည်။ ဒီနေရာမှာနှစ်ထပ်ကွမ်းစာရင်းထဲတွင်ထည့်သွင်းခြင်းနှင့်ဖျက်ခြင်းအတွင်းအချို့သောအပိုအမှတ်အသားများကိုပြင်ဆင်ရန်လိုအပ်သည်။
အယူအဆသည်ထပ်တူထပ်မျှချိတ်ဆက်ထားသောစာရင်းကို ဦး စားပေးအစီအစဉ်အတိုင်းလျှော့ချရန်ဆက်လက်ထိန်းသိမ်းထားရန်ဖြစ်သည်။ သို့မှသာအမြင့်ဆုံး ဦး စားပေးဒြပ်စင်သည်အမြဲတမ်းရှေ့တွင်ရှိသည်။

တွန်းအားပေး (x, p)

Element တစ်ခုကို x နှင့် ဦး စားပေး p အားဖြင့် Queue ထဲသို့ထည့်ရန်၎င်းအတွက်သင့်တော်သောနေရာကိုရှာပြီးထည့်ပါ။ သင့်လျော်သောနေရာသည် p ထက်နည်းသော ဦး စားပေးမှုဖြင့်ပထမ element မတိုင်မီလေးတွင်ရှိသည်။

ဥပမာ,
PriorityQueue = (၇၊ ၅) -> (၉၊၄) -> (၈၊ ၂)
တွန်း (6, 3)
(၆၊ ၃) အတွက်သင့်တော်သောနေရာသည် (၈၊ ၂) မတိုင်မီလေးတွင်ဖြစ်ပြီး၊
priorQueue = (7, 5) -> (9, 4) -> (6, 3) -> (8, 2)
ရှင်းလင်းချက်အတွက်အောက်ပါပုံကိုကြည့်ပါ။

နှစ်ထပ်ဆက်ထားသောစာရင်းကို အသုံးပြု၍ ဦး စားပေးတန်းစီသည်

  1. အတွက်လမ်းကြောင်း ဦး စားပေးတန်းစီ ဦး ခေါင်းမှ စတင်၍ p ထက်နည်းသော ဦး စားပေးပထမ ဦး ဆုံး node ကိုရှာပါ။
  2. ရောဂါသုံးမျိုးထဲကတစ်ခုဖြစ်နိုင်ပါတယ်။
  3. p ထက်လျော့နည်း ဦး စားပေးနှင့်အတူအဘယ်သူမျှမဒြပ်စင်မရှိပါ။ ထိုကဲ့သို့သောအမှု၌ ဦး စားပေးတန်းစီ၏အဆုံးမှာ node ကိုအသစ်ထည့်ပါ။
  4. ဆုံမှတ်များအားလုံးသည် p ထက်နည်းသည်။ ထိုကဲ့သို့သောအမှု၌ ဦး စားပေးတန်းစီ၏အစအ ဦး မှာ node ကိုအသစ်ထည့်ပါ။
  5. p ထက် ဦး စားပေးသော node အချို့ရှိပြီး p ထက် ပို၍ ဦး စားပေးသော node အချို့ရှိသည်။ ထိုကဲ့သို့သောကိစ္စမျိုးတွင် p ထက်နည်းသော ဦး စားပေးနှင့်ပထမ node မတိုင်မီ node အသစ်ကိုထည့်ပါ။ ဤကိစ္စကိုအပေါ်ကပုံမှာပြထားပါတယ်။

အချိန်ရှုပ်ထွေး = အို (ဎ)
အာကာသရှုပ်ထွေးမှု = အို (၁)
n သည် insertion မတိုင်မီ ဦး စားပေးတန်းစီတွင် node စုစုပေါင်းအရေအတွက်။

ပေါ့ပ် ()

အမြင့်ဆုံး ဦး စားပေးဒြပ်စင် ဦး စားပေးတန်းစီ၏အစမှာပစ္စုပ္ပန်ဖြစ်ပါတယ်။ ဦး စားပေးတန်းစီသည်အချည်းနှီးမဟုတ်ပါကပထမ element ကို ဖျက်၍ ပြန်ပို့ပါ။ ၎င်းသည် pop မလုပ်နိုင်ပါ။

အချိန်ရှုပ်ထွေး = အို (၁)

peek ()

အမြင့်ဆုံး ဦး စားပေးဒြပ်စင် ဦး စားပေးတန်းစီ၏အစမှာပစ္စုပ္ပန်ဖြစ်ပါတယ်။ အကယ်၍ Priority Queue သည်အလွတ်မဖြစ်ပါက၊ ပထမတန်း၏ပထမ element ၏တန်ဖိုးကို return ပြန်ပေးပါ။

အချိန်ရှုပ်ထွေး = အို (၁)

ကုဒ်

Two-link list ကို သုံး၍ Priority Queue ကိုအကောင်အထည်ဖော်ရန် Java Code

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

နှစ်ထပ်ချိတ်ထားသောစာရင်းကို အသုံးပြု၍ Priority Queue ကိုအကောင်အထည်ဖော်ရန် 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