प्राथमिकता पked्क्ति एकल लिked्क गरिएको सूची प्रयोग गरेर


कठिनाई तह मध्यम
बारम्बार सोधिन्छ ब्राउजरस्ट्याक Hulu महिन्द्रा Comviva पकेट रत्न सोरोको
लिंक्ड-सूची लाम

प्राथमिकतामा लाम एकल प्रयोग गर्दै लिंक गरिएको सूची समस्या, हामी एकल लिंक गरिएको सूची प्रयोग गरेर प्राथमिकता लाम लागू गर्न आवश्यक छ। प्राथमिकता पue्क्तिले निम्न अपरेशनहरू समावेश गर्दछ,

  1. पुश (x, p): प्राथमिकता पue्क्तिमा उचित स्थितिमा प्राथमिकता p सहित एक तत्व x थप्नुहोस्।
  2. पप (): उच्च प्राथमिकताका साथ एलिमेन्ट हटाउनुहोस् र फिर्ता गर्नुहोस्
  3. पिक (): उच्च प्राथमिकताको साथ तत्व फर्काउनुहोस्

उदाहरणका

इनपुट:
धक्का (,, २)
धक्का (,, २)
झलक ()
धक्का (,, २)
धक्का (,, २)
पप ()
पप ()
झलक ()
उत्पादन:
1
7
1
5

एकल लिंक गरिएको सूची प्रयोग गरेर प्राथमिकता लाममा एल्गोरिथ्म

विचार यो छ कि लि list्क गरिएको सूची प्राथमिकताको अवरोही क्रममा कायम राख्नुहोस् ताकि उच्च प्राथमिकता तत्त्व अगाडि हो।

धक्का (x, p)

जस्तो कि तत्वहरू प्राथमिकताको क्रममा क्रमबद्ध गरिएको छ, त्यसैले प्राथमिकता पीको साथ पहिलो तत्व p भन्दा कम प्राथमिकताको साथ पहिले सम्मिलित हुन्छ, ताकि प्राथमिकताको क्रम बिघ्न नहोस्। तीनवटा मुद्दा खडा हुन्छन्,

  1. पी भन्दा कम प्राथमिकताको साथ कुनै एलिमेन्ट छैन, लिंक गरिएको सूचीको अन्त्यमा नयाँ एलिमेन्ट जोड्नुहोस्।
  2. सबै तत्वहरूको p भन्दा कम प्राथमिकता हुन्छ, लि list्क गरिएको सूचीको सुरूमा नयाँ तत्व थप्नुहोस्।
  3. केहि तत्वहरू पी भन्दा कम प्राथमिकता हुन्छन् भने अरूसँग पी भन्दा प्राथमिकता हुन्छ, नयाँ तत्व थप्नुहोस् पहिलो तत्त्व अघि p भन्दा कम प्राथमिकता पाउनुहोस्।

प्राथमिकता पked्क्ति एकल लिked्क गरिएको सूची प्रयोग गरेर

समय जटिलता = ऊ)

एकल लिंक गरिएको सूची प्रयोग गरेर प्राथमिकता लामको लागि स्यूडो कोड

  1. डाटा = x र प्राथमिकता = p को साथ नयाँ नोड बनाउनुहोस्, यसलाई नयाँ नोड हुन दिनुहोस्
  2. यदि शिर शून्य छ भने, यो घुसाउनको लागि पहिलो नोड हो, त्यसैले हेड = newNode बनाउनुहोस् र फर्कनुहोस्।
  3. एक नोड अस्थायी बराबर हेड सिर्जना गर्नुहोस् र एक नोड prev नल बराबर।
  4. प्राथमिकतासँग पहिलो नोड पत्ता लगाउनुहोस् p भन्दा कम लूप चलाएर जबकि टेम्प खाली छैन र अस्थायी प्राथमिकता p भन्दा ठूलो छ। प्रत्येक पुनरावृत्तिमा, अस्थायी रूपमा टेम्प र टेम्प टेम्प्नेन्टको रूपमा अध्यावधिक गर्नुहोस्।
  5. लूपको अन्त्य पछि, यदि अस्थायी शून्य छ भने, यसको मतलब त्यहाँ पी भन्दा कम प्राथमिकता भएको कुनै नोड छैन, लि list्क गरिएको सूचीको अन्त्यमा नयाँ नोड घुसाउनुहोस्, जुन गर्नुहोस्, prev.next = newNode।
  6. अन्य यदि यदि पूर्व शून्य छ भने, यसले स that्केत गर्दछ कि सबै नोडहरू पी भन्दा ठूलो प्राथमिकतामा छन्। NewNode.next = हेड र हेड = newNode गर्नुहोस्।
  7. अर्को, अस्थायी भन्दा पहिले नयाँ नोड घुसाउनुहोस्, त्यो हो, newNode.next = अस्थायी र prev.next = newNode गर्नुहोस्।

पप ()

लि list्क गरिएको सूचीको अगाडि उच्च प्राथमिकता तत्व समावेश गर्दछ, यसलाई हटाउनुहोस्, र फर्कनुहोस्।

समय जटिलता = O (१)

झलक ()

लिंक गरिएको सूचीको अगाडि उच्च प्राथमिकता तत्व समावेश गर्दछ, यो फिर्ता गर्नुहोस्।

समय जटिलता = O (१)

एकल लिंक गरिएको सूची प्रयोग गरेर प्राथमिकता लामको लागि जाभा कोड

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

सी ++ एकल लिंक गरिएको सूची प्रयोग गरेर प्राथमिकता लामको लागि कोड

#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    सन्दर्भ २