단일 연결 목록을 사용하는 우선 순위 대기열

난이도 중급
자주 묻는 질문 BrowserStack 훌루 마힌 드라 콤비 바 포켓 보석 소로코
연결된 목록 조회수 49

우선 변발 단독으로 사용 연결 목록 문제, 우리는 단일 연결 목록을 사용하여 우선 순위 대기열을 구현해야합니다. 우선 순위 대기열에는 다음 작업이 포함됩니다.

  1. push (x, p) : 우선 순위 큐의 적절한 위치에 우선 순위가 p 인 요소 x를 추가합니다.
  2. pop () : 우선 순위가 가장 높은 요소를 제거하고 반환
  3. peek () : 우선 순위가 가장 높은 요소를 반환합니다.

입력:
푸시 (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. data = x 및 priority = p 인 새 노드를 만들고 newNode로 둡니다.
  2. 헤드가 null 인 경우 삽입 할 첫 번째 노드이므로 head = newNode로 만들고 반환합니다.
  3. 노드 temp는 head와 같고 노드 prev는 null과 같습니다.
  4. temp가 null이 아니고 temp의 우선 순위가 p보다 큰 동안 루프를 실행하여 우선 순위가 p보다 작은 첫 번째 노드를 찾습니다. 반복 할 때마다 prev를 temp로, temp를 temp.next로 업데이트합니다.
  5. 루프 종료 후 temp가 null이면 우선 순위가 p보다 작은 노드가 없음을 의미하며, 연결 목록의 끝에 newNode를 삽입합니다. 즉, do prev.next = newNode입니다.
  6. 그렇지 않으면 prev가 null이면 모든 노드의 우선 순위가 p보다 크다는 것을 의미합니다. newNode.next = head 및 head = 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

Translate »