రెట్టింపు లింక్ చేసిన జాబితాను ఉపయోగించి ప్రాధాన్యత క్యూ


కఠినత స్థాయి మీడియం
తరచుగా అడుగుతుంది అమెజాన్ సిటాడెల్ మాక్య్ వూకర్
లింక్డ్-జాబితా ప్రాధాన్యతా క్యూ క్యూ

సమస్యల నివేదిక

“రెట్టింపు లింక్డ్ జాబితాను ఉపయోగించి ప్రాధాన్యత క్యూ” సమస్య రెట్టింపు ఉపయోగించి ప్రాధాన్యతా క్యూ యొక్క క్రింది విధులను అమలు చేయమని అడుగుతుంది లింక్ చేసిన జాబితా.

  1. పుష్ (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

రెట్టింపు లింక్ జాబితాను ఉపయోగించి ప్రాధాన్యతా క్యూను అమలు చేయడానికి అల్గోరిథం

ప్రాధాన్యతా క్యూ రెట్టింపు లింక్డ్ జాబితాను ఉపయోగించడం అనేది ఏకైక లింక్ చేయబడిన జాబితాను ఉపయోగించి ప్రాధాన్యత క్యూ వలె అమలు చేయబడుతుంది. ఇక్కడ రెట్టింపు లింక్ చేయబడిన జాబితాలో మేము చొప్పించడం మరియు తొలగించేటప్పుడు కొన్ని అదనపు పాయింటర్లను సవరించాలి.
ప్రాధాన్యత క్రమాన్ని తగ్గించడంలో రెట్టింపు అనుసంధాన జాబితాను నిర్వహించడం ఆలోచన అదే, తద్వారా అత్యధిక ప్రాధాన్యత మూలకం ఎల్లప్పుడూ ముందు ఉంటుంది.

పుష్ (x, p)

ప్రాధాన్యత క్యూతో ఒక మూలకం x ను ప్రాధాన్యతా క్యూలో నెట్టడానికి, మూలకానికి తగిన స్థలాన్ని కనుగొని, దాన్ని చొప్పించండి. P కంటే తక్కువ ప్రాధాన్యత కలిగిన మొదటి మూలకానికి ముందు తగిన స్థలం.

ఉదాహరణకి,
ప్రాధాన్యత క్యూ = (7, 5) -> (9, 4) -> (8, 2)
పుష్ (6, 3)
(6, 3) కి తగిన స్థలం ముందు (8, 2), చొప్పించిన తర్వాత క్యూ,
ప్రాధాన్యత క్యూ = (7, 5) -> (9, 4) -> (6, 3) -> (8, 2)
స్పష్టత కోసం క్రింది చిత్రాన్ని చూడండి.

రెట్టింపు లింక్ చేసిన జాబితాను ఉపయోగించి ప్రాధాన్యత క్యూ

  1. లో ప్రయాణించండి ప్రాధాన్యత క్యూ తల నుండి ప్రారంభించి, p కంటే తక్కువ ప్రాధాన్యత కలిగిన మొదటి నోడ్‌ను కనుగొనండి.
  2. మూడు కేసులలో ఒకటి సాధ్యమే.
  3. P కంటే తక్కువ ప్రాధాన్యత ఉన్న మూలకం లేదు. అటువంటి సందర్భంలో ప్రాధాన్యత క్యూ చివరిలో కొత్త నోడ్‌ను చొప్పించండి.
  4. అన్ని నోడ్లకు p కంటే తక్కువ ప్రాధాన్యతలు ఉన్నాయి. అటువంటి సందర్భంలో ప్రాధాన్యత క్యూ ప్రారంభంలో కొత్త నోడ్‌ను చొప్పించండి.
  5. P కంటే తక్కువ ప్రాధాన్యత కలిగిన కొన్ని నోడ్‌లు మరియు p కంటే ఎక్కువ ప్రాధాన్యత కలిగిన కొన్ని నోడ్‌లు ఉన్నాయి. అటువంటి సందర్భంలో p కంటే తక్కువ ప్రాధాన్యతతో మొదటి నోడ్‌కు ముందు కొత్త నోడ్‌ను చొప్పించండి. ఈ కేసు పై చిత్రంలో చూపబడింది.

సమయం సంక్లిష్టత = పై)
అంతరిక్ష సంక్లిష్టత = O (1)
ఇక్కడ n అనేది చొప్పించే ముందు ప్రాధాన్యత క్యూలోని మొత్తం నోడ్‌ల సంఖ్య.

పాప్()

ప్రాధాన్యతా క్యూ ప్రారంభంలో అత్యధిక ప్రాధాన్యత మూలకం ఉంటుంది. ప్రాధాన్యత క్యూ ఖాళీగా లేకపోతే మొదటి మూలకాన్ని తొలగించి తిరిగి ఇవ్వండి, లేకపోతే పాప్ చేయడం సాధ్యం కాదు.

సమయ సంక్లిష్టత = O (1)

పీక్ ()

ప్రాధాన్యతా క్యూ ప్రారంభంలో అత్యధిక ప్రాధాన్యత మూలకం ఉంటుంది. ప్రాధాన్యత క్యూ ఖాళీగా లేకపోతే ప్రాధాన్యత క్యూలోని మొదటి మూలకం విలువను తిరిగి ఇవ్వండి.

సమయ సంక్లిష్టత = O (1)

కోడ్

రెట్టింపు లింక్ జాబితాను ఉపయోగించి ప్రాధాన్యతా క్యూను అమలు చేయడానికి జావా కోడ్

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

రెట్టింపు లింక్ జాబితాను ఉపయోగించి ప్రాధాన్యతా క్యూను అమలు చేయడానికి సి ++ కోడ్

#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