Давхар холбоос бүхий жагсаалтыг ашиглан тэргүүлэх дараалал


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Citadel MAQ Wooker
Холбогдсон жагсаалт Тэргүүлэх дараалал дараалал

Асуудлын мэдэгдэл

Асуудал нь "Давхар холбоос бүхий жагсаалтыг ашиглан тэргүүлэх дараалал" гэсэн дарааллыг ашиглан дараахь дарааллын дарааллыг хэрэгжүүлэхийг хүсч байна холбоотой жагсаалт.

  1. түлхэх (x, p) : X элементийг тохирох байрлал дахь тэргүүлэх дараалалд 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)

код

Давхар холбоос бүхий жагсаалтыг ашиглан тэргүүлэх дарааллыг хэрэгжүүлэх 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