Приоритетни ред помоћу појединачно повезане листе


Ниво тешкоће Средњи
Често питани у БровсерСтацк Хулу Махиндра Цомвива Поцкет Гемс Сороцо
Повезана листа Ред

Приоритетно ред користећи појединачно повезана листа проблем, морамо да применимо приоритетни ред помоћу појединачно повезане листе. Приоритетни ред садржи следеће операције,

  1. пусх (к, п): Додајте елемент к са приоритетом п на одговарајуће место у реду приоритета.
  2. поп (): Уклоните и вратите елемент са највишим приоритетом
  3. пеек (): Врати елемент са највишим приоритетом

Пример

Улаз:
гурање (5, 2)
гурање (1, 3)
завирити ()
гурање (7, 5)
гурање (9, 1)
поп ()
поп ()
завирити ()
Излаз:
1
7
1
5

Алгоритам за приоритетни ред помоћу појединачно повезане листе

Идеја је да се везана листа одржи у опадајућем редоследу приоритета тако да елемент са највишим приоритетом буде испред.

гурање (к, п)

Како су елементи распоређени у падајућем редоследу приоритета, тако се и елемент са приоритетом п убацује испред првог елемента са приоритетом мањим од п, тако да се редослед приоритета не нарушава. Појављују се три случаја,

  1. Ниједан елемент са приоритетом мањим од п, додајте нови елемент на крај повезане листе.
  2. Сви елементи имају приоритет мањи од п, додајте нови елемент на почетку повезане листе.
  3. Неки елементи имају приоритет мањи од п, док други имају приоритет већи од п, додајте нови елемент пре првог елемента који има приоритет мањи од п.

Приоритетни ред помоћу појединачно повезане листе

Сложеност времена = Он)

Псеудо код за приоритетни ред помоћу појединачно повезане листе

  1. Направите нови чвор са подацима = к и приоритетом = п, нека буде невНоде
  2. Ако је глава нулл, ово је први чвор који се убацује, па направите хеад = невНоде и вратите се.
  3. Направите чвор темп једнак глави и чвор прев једнак нули.
  4. Пронађите први чвор са приоритетом мањим од п покретањем петље док темп није нулл и приоритет темп је већи од п. На свакој итерацији ажурирајте прев као темп и темп као темп.нект.
  5. Након завршетка петље, ако је привремена вредност нулл, то значи да не постоји чвор са приоритетом мањим од п, убаците невНоде на крај повезане листе, односно урадите прев.нект = невНоде.
  6. Иначе ако је прев нулл, то подразумева да сви чворови имају приоритет већи од п. Урадите невНоде.нект = хеад и хеад = невНоде.
  7. У супротном, уметните нови чвор пре темп, то јест урадите невНоде.нект = темп и прев.нект = невНоде.

поп ()

Предња страна повезане листе садржи елемент највишег приоритета, уклоните га и вратите.

Сложеност времена = О (1)

завирити ()

Предња страна повезане листе садржи елемент највишег приоритета, вратите га.

Сложеност времена = О (1)

ЈАВА код за приоритетни ред помоћу појединачно повезане листе

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    референце2