우선 변발 단독으로 사용 연결 목록 문제, 우리는 단일 연결 목록을 사용하여 우선 순위 대기열을 구현해야합니다. 우선 순위 대기열에는 다음 작업이 포함됩니다.
- push (x, p) : 우선 순위 큐의 적절한 위치에 우선 순위가 p 인 요소 x를 추가합니다.
- pop () : 우선 순위가 가장 높은 요소를 제거하고 반환
- peek () : 우선 순위가 가장 높은 요소를 반환합니다.
차례
예
입력:
푸시 (5, 2)
푸시 (1, 3)
몰래 엿보다()
푸시 (7, 5)
푸시 (9, 1)
팝()
팝()
몰래 엿보다()
출력:
1
7
1
5
단일 연결 목록을 사용하는 우선 순위 대기열 알고리즘
아이디어는 가장 높은 우선 순위 요소가 맨 앞에 오도록 연결 목록을 우선 순위의 내림차순으로 유지하는 것입니다.
푸시 (x, p)
우선 순위의 내림차순으로 배열되어 있으므로 우선 순위가 p보다 작은 첫 번째 요소보다 우선 순위가 p 인 요소가 먼저 삽입되므로 우선 순위의 순서를 방해하지 않는다. 세 가지 경우가 발생합니다.
- 우선 순위가 p보다 작은 요소가 없습니다. 연결 목록 끝에 새 요소를 추가하십시오.
- 모든 요소의 우선 순위가 p보다 작 으면 연결 목록의 시작 부분에 새 요소를 추가합니다.
- 일부 요소는 p보다 낮은 우선 순위를 갖는 반면 다른 요소는 p보다 높은 우선 순위를 갖습니다. 우선 순위가 p보다 작은 첫 번째 요소 앞에 새 요소를 추가하십시오.
시간 복잡성 = O (N)
단일 연결 목록을 사용하는 우선 순위 대기열에 대한 의사 코드
- data = x 및 priority = p 인 새 노드를 만들고 newNode로 둡니다.
- 헤드가 null 인 경우 삽입 할 첫 번째 노드이므로 head = newNode로 만들고 반환합니다.
- 노드 temp는 head와 같고 노드 prev는 null과 같습니다.
- temp가 null이 아니고 temp의 우선 순위가 p보다 큰 동안 루프를 실행하여 우선 순위가 p보다 작은 첫 번째 노드를 찾습니다. 반복 할 때마다 prev를 temp로, temp를 temp.next로 업데이트합니다.
- 루프 종료 후 temp가 null이면 우선 순위가 p보다 작은 노드가 없음을 의미하며, 연결 목록의 끝에 newNode를 삽입합니다. 즉, do prev.next = newNode입니다.
- 그렇지 않으면 prev가 null이면 모든 노드의 우선 순위가 p보다 크다는 것을 의미합니다. newNode.next = head 및 head = newNode를 수행하십시오.
- 그렇지 않으면 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