ഇരട്ടി ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിക്കുന്ന മുൻ‌ഗണന ക്യൂ  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ കോട്ട MAQ വുക്കർ
ലിങ്ക്ഡ്-ലിസ്റ്റ് മുൻ‌ഗണനാ ക്യൂ വരി

പ്രശ്നം പ്രസ്താവന  

“ഇരട്ട ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിക്കുന്ന മുൻ‌ഗണന ക്യൂ” എന്ന പ്രശ്‌നം ഇരട്ടി ഉപയോഗിച്ച് മുൻ‌ഗണനാ ക്യൂവിന്റെ ഇനിപ്പറയുന്ന പ്രവർത്തനങ്ങൾ നടപ്പിലാക്കാൻ ആവശ്യപ്പെടുന്നു ലിങ്കുചെയ്‌ത ലിസ്റ്റ്.

  1. പുഷ് (x, p) : ഉചിതമായ സ്ഥാനത്ത് മുൻ‌ഗണന ക്യൂവിൽ‌ മുൻ‌ഗണനാ p ഉള്ള ഒരു ഘടകം എൻ‌ക്യൂ ചെയ്യുക.
  2. പോപ്പ് () : മുൻ‌ഗണനാ ക്യൂവിൽ‌ ഉയർന്ന മുൻ‌ഗണനയുള്ള ഘടകം നീക്കംചെയ്‌ത് തിരികെ നൽകുക.
  3. പീക്ക് () : മുൻ‌ഗണന ക്യൂവിൽ‌ നീക്കംചെയ്യാതെ തന്നെ മുൻ‌ഗണന നൽ‌കുക.

ഉദാഹരണം  

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

ഇരട്ട ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിച്ച് മുൻ‌ഗണനാ ക്യൂ നടപ്പിലാക്കുന്നതിനുള്ള അൽ‌ഗോരിതം  

മുൻ‌ഗണനാ ക്യൂ സിംഗിൾ ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിച്ച് മുൻ‌ഗണനാ ക്യൂ പോലെ തന്നെ ഇരട്ട ലിങ്കുചെയ്‌ത ലിസ്റ്റ് ഉപയോഗിക്കുന്നത് നടപ്പിലാക്കുന്നു. ഇവിടെ ഇരട്ട ലിങ്കുചെയ്‌ത ലിസ്റ്റിൽ ഉൾപ്പെടുത്തലിനും ഇല്ലാതാക്കലിനുമായി ചില അധിക പോയിന്ററുകൾ ഞങ്ങൾ പരിഷ്‌ക്കരിക്കേണ്ടതുണ്ട്.
മുൻ‌ഗണന ക്രമം കുറയ്ക്കുന്നതിന് ഇരട്ട ലിങ്കുചെയ്‌ത ലിസ്റ്റ് നിലനിർത്തുന്നതിന് ആശയം സമാനമാണ്, അതിനാൽ ഉയർന്ന മുൻ‌ഗണനാ ഘടകം എല്ലായ്പ്പോഴും മുൻ‌പന്തിയിലാണ്.

പുഷ് (x, p)

മുൻ‌ഗണനാ ക്യൂ ഉള്ള ഒരു ഘടകം മുൻ‌ഗണനാ ക്യൂവിലേക്ക് നീക്കുന്നതിന്, ഘടകത്തിന് അനുയോജ്യമായ സ്ഥലം കണ്ടെത്തി അത് തിരുകുക. 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 (n)
ബഹിരാകാശ സങ്കീർണ്ണത = 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