Приоритетная очередь с использованием двусвязного списка


Сложный уровень средний
Часто спрашивают в Амазонка Цитадель MAQ Wooker
Связанный список Приоритетная очередь Очередь

Постановка задачи

Задача «Приоритетная очередь с использованием двусвязного списка» предлагает реализовать следующие функции приоритетной очереди с использованием двусвязного списка. связанный список.

  1. толкать (х, р) : Поставить элемент x с приоритетом p в очередь с приоритетом в соответствующей позиции.
  2. поп () : Удалить и вернуть элемент с наивысшим приоритетом в очереди приоритетов.
  3. заглянуть () : Вернуть элемент с наивысшим приоритетом в очередь приоритетов, не удаляя его.

Пример

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

Алгоритм реализации Priority Queue с использованием двусвязного списка

Приоритетная очередь Использование двусвязного списка реализовано так же, как приоритетная очередь с использованием односвязного списка. Здесь, в двусвязном списке, мы должны изменить некоторые дополнительные указатели во время вставки и удаления.
Идея та же, поддерживать двусвязный список в порядке убывания приоритета, чтобы элемент с наивысшим приоритетом всегда находился впереди.

толкать (х, р)

Чтобы поместить элемент x с приоритетом p в очередь с приоритетом, найдите подходящее место для элемента и вставьте его. Подходящее место - непосредственно перед первым элементом с приоритетом меньше p.

Например,
priorityQueue = (7, 5) -> (9, 4) -> (8, 2)
Нажать (6, 3)
Подходящее место для (6, 3) - непосредственно перед (8, 2), очередь после вставки:
priorityQueue = (7, 5) -> (9, 4) -> (6, 3) -> (8, 2)
См. Изображение ниже для пояснения.

Приоритетная очередь с использованием двусвязного списка

  1. Траверс в приоритетная очередь начиная с головы и найдите первый узел с приоритетом меньше p.
  2. Возможен один из трех случаев.
  3. Нет элемента с приоритетом меньше p. В таком случае вставьте новый узел в конец очереди приоритетов.
  4. Все узлы имеют приоритет меньше p. В таком случае вставьте новый узел в начало очереди приоритетов.
  5. Есть некоторые узлы с приоритетом меньше p и некоторые узлы с приоритетом больше p. В таком случае вставьте новый узел перед первым узлом с приоритетом меньше p. Этот случай показан на изображении выше.

Сложность времени = О (п)
Космическая сложность = 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