תור עדיפות באמצעות רשימה מקושרת בודדת  


רמת קושי בינוני
נשאל לעתים קרובות BrowserStack Hulu מהינדרה קומביווה אבני חן כיס סורוקו
רשימה מקושרת תור

בעדיפות תור באמצעות יחיד רשימה מקושרת בעיה, עלינו ליישם תור עדיפות באמצעות רשימה המקושרת יחידה. תור עדיפות מכיל את הפעולות הבאות,

  1. דחיפה (x, p): הוסף אלמנט x עם עדיפות p במיקום מתאים בתור העדיפות.
  2. pop (): הסר והחזיר את האלמנט בעדיפות הגבוהה ביותר
  3. הצצה (): להחזיר את האלמנט בעדיפות הגבוהה ביותר

דוגמה  

קלט:
לדחוף (5, 2)
לדחוף (1, 3)
לְהָצִיץ()
לדחוף (7, 5)
לדחוף (9, 1)
פּוֹפּ()
פּוֹפּ()
לְהָצִיץ()
פלט:
1
7
1
5

אלגוריתם לתור עדיפות באמצעות רשימה מקושרת בודדת  

הרעיון הוא לשמור על הרשימה המקושרת בסדר עדיפות יורד כך שאלמנט העדיפות הגבוה ביותר יהיה בחזית.

לדחוף (x, p)

מכיוון שהאלמנטים מסודרים לפי סדר עדיפויות יורד, כך אלמנט עם עדיפות p מוכנס לפני האלמנט הראשון עם עדיפות פחות מ- p, כך שסדר העדיפויות לא יופרע. שלושה מקרים מתעוררים,

  1. אין אלמנט עם עדיפות נמוכה מ- p, הוסף את האלמנט החדש בסוף הרשימה המקושרת.
  2. לכל האלמנטים עדיפות פחות מ- p, הוסף את האלמנט החדש בתחילת הרשימה המקושרת.
  3. לחלק מהאלמנטים יש עדיפות פחות מ- p ואילו לאחרים יש עדיפות יותר מ- p, הוסף את האלמנט החדש לפני שהאלמנט הראשון בעל עדיפות נמוכה מ- p
ראה גם
טופס מספר מינימלי מרצף נתון

תור עדיפות באמצעות רשימה מקושרת בודדתאורן

מורכבות זמן = O (n)

קוד פסאודו לתור עדיפות באמצעות רשימה מקושרת בודדת  

  1. הכינו צומת חדש עם נתונים = x ועדיפות = p, שיהיה newNode
  2. אם הראש הוא אפס, זהו הצומת הראשון שהוכנס, אז בצעו head = newNode וחזרו.
  3. צור צומת זמני שווה לראש וצומת הקוד שווה לאפס.
  4. מצא את הצומת הראשון עם עדיפות פחות מ- p על ידי הפעלת לולאה בזמן שהטמפ 'אינו אפס והעדיפות של טמפ' גדולה מ- p. בכל איטרציה, עדכן קודם כמו temp ו- temp כמו temp.next.
  5. לאחר סיום הלולאה, אם הטמפ 'הוא אפס, המשמעות היא שאין צומת עם עדיפות נמוכה מ- p, הכנס את ה- newNode בסוף הרשימה המקושרת, כלומר, עשה קודמים = newNode.
  6. אחרת אם הקוד הוא אפס, זה מרמז על כך שכל הצמתים הם בעלי עדיפות גדולה מ- p. בצע newNode.next = ראש וראש = newNode.
  7. אחרת, הכנס את הצומת החדש לפני temp, כלומר בצע newNode.next = temp ו prev.next = newNode.

פּוֹפּ()

חזית הרשימה המקושרת מכילה את אלמנט העדיפות הגבוהה ביותר, הסר אותו והחזר.

מורכבות זמן = O (1)

לְהָצִיץ()

חזית הרשימה המקושרת מכילה את אלמנט העדיפות הגבוהה ביותר, החזירו אותו.

מורכבות זמן = O (1)

קוד JAVA לתור עדיפות באמצעות רשימה מקושרת בודדת  

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

קוד C ++ לתור עדיפות באמצעות רשימה מקושרת בודדת  

#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