데이터 구조에서 우선 순위 대기열을 구현하는 방법은 무엇입니까?

Bikash Daga·2022년 3월 29일
1

data-structures

목록 보기
1/1
post-thumbnail

소개

제출할 과제가 4개 있다고 가정합니다.

  1. 데이터베이스 관리 시스템
  2. 물리학
  3. 객체 지향 프로그래밍
  4. 수학

DBMS 및 객체 지향 프로그래밍 과제는 월요일에 제출해야 합니다. 화요일에는 물리 과제, 수요일에는 수학 과제. 따라서 귀하의 우선 순위는 DBMS 및 OOPS 할당을 완료하는 것입니다. 따라서 제출 날짜에 따라 우선 순위를 결정합니다.

이러한 맥락에서 우선순위 큐의 개념과 구현을 이해합시다.

우선 순위 대기열

우선 순위 대기열은 모든 요소에 특정 우선 순위 값이 있는 특수한 유형의 대기열입니다. 요소의 우선 순위는 대기열의 순서에 영향을 줍니다. 따라서 우선 순위가 높은 요소가 다른 요소보다 우선 순위가 높습니다.

동일한 우선 순위를 가진 요소는 대기열에 배치된 순서대로 처리됩니다.

요소에 우선 순위를 지정할 때 일반적으로 요소 자체의 값이 고려됩니다. 예를 들어 우선 순위는 가장 높은 값을 가진 요소에 의해 결정됩니다. 다른 경우에는 가장 중요한 요소를 가장 낮은 값의 요소로 간주할 수 있습니다. 필요에 따라 우선 순위를 설정할 수도 있습니다.

우선순위 큐의 특징

다음은 우선순위 큐의 특성입니다.

  1. 대기열의 각 요소는 비교 가능해야 합니다.
  2. 대기열의 모든 항목에 우선 순위가 지정되어야 합니다.
  3. 사용자가 더 낮은 숫자를 더 높은 우선순위로 또는 더 높은 숫자를 더 높은 우선순위로 간주하는 경우 더 높은 우선순위 요소 또는 더 낮은 우선순위 요소가 더 낮거나 더 높은 우선순위 요소보다 먼저 큐에서 제거되어야 합니다.
  4. 우선순위 큐에서 같은 우선순위 값을 가진 두 개의 요소는 추가된 순서대로 제거됩니다. 즉, 우선순위 큐에 먼저 들어간 요소가 먼저 제거되어야 함을 의미합니다.

우선순위 큐의 유형

우선 순위에 따라 두 가지 유형의 우선 순위 대기열이 있습니다.

  • 오름차순 - 앞에서 언급했듯이 우선 순위 대기열의 요소는 비교할 수 있어야 합니다. 즉, 서로 작거나 같거나 커야 합니다. 오름차순 우선 순위 대기열에서 모든 요소는 서로 비교되며 다음 규칙을 따릅니다.

    요소(숫자)가 작을수록 높은 우선 순위가 적용됩니다.

  • 내림차순 - 대기열의 각 요소는 다음 규칙에 따라 내림차순으로 다음 요소와 비교됩니다.

    요소(숫자)가 클수록 우선 순위가 높아집니다.

데이터 구조에서 우선순위 큐의 구현

데이터 구조에서 큐를 구현할 수 있는 네 가지 방법이 있습니다.

  • 연결 리스트 : 우선 순위 척도에서 더 높은 순위의 요소가 연결 리스트의 맨 위에 위치합니다. 다음 단계에서는 우선 순위에 따라 목록의 모든 요소에 내림차순이 적용됩니다.

    클래스 선언:

    정적 클래스 PNode {
      정수 데이터;
      정수 우선 순위;
      노드 다음;
    }

    연결 리스트의 전체 순서를 유지하기 위해 적절한 위치가 식별될 때까지 리스트를 순회하여 리스트에 요소를 삽입하기에 적합한 위치를 찾습니다. 따라서 목록의 모든 요소를 ​​순회하는 데 시간이 가장 오래 걸리므로 최악의 경우는 O(n)입니다.

CPP 코드

#include <비트/stdc++.h>
네임 스페이스 표준 사용;

typedef 구조체 노드 // 노드 생성
{
정수 데이터; // 노드의 값
정수 우선 순위; // 낮은 값 = 높은 우선순위
구조체 노드* 다음; // 다음 노드에 대한 포인터

} 노드;

Node* newNode(int d, int p) // 새 노드를 생성하는 함수
{
노드* 임시 = (노드*)malloc(sizeof(노드)); // 노드의 크기 할당
임시 -> 데이터 = d; // 데이터 값 초기화
임시 -> 우선 순위 = p; // 우선순위 값 초기화
임시 -> 다음 = NULL;

반환 온도;
}

int peek(Node** head) // 헤드 노드 인쇄
{
반환 (* 헤드)-> 데이터;
}

void pop(Node** head) // 우선 순위가 가장 높은 요소 제거
{
노드* 온도 = *헤드;
(*머리) = (*머리)->다음;
무료(임시);
}

void push(Node** head, int d, int p) // 우선순위에 따라 노드를 삽입
{
노드* 시작 = (*헤드);
노드* 임시 = newNode(d, p); // 새로운 노드 생성

// 특별한 경우: 목록의 헤드는
// 새 노드보다 우선 순위가 낮습니다. 그래서
// 헤드 노드 앞에 newnode 삽입
// 헤드 노드를 변경합니다.
if ((*head)->우선순위 > p)
{

임시 -> 다음 = * 머리; // 헤드 앞에 새 노드 삽입
(* 헤드) = 온도;
}
또 다른
{


while (start->next != NULL && start->next->priority < p) // 노드에 들어갈 적절한 위치를 찾습니다.
{
시작 = 시작->다음;
}

// 목록의 끝에서
// 또는 필요한 위치에
임시 -> 다음 = 시작 -> 다음;
시작 -> 다음 = 임시;
}
}

// 확인할 함수는 목록이 비어 있는지 확인합니다.
int isEmpty(노드** 헤드)
{
반환 (* 헤드) == NULL;
}

정수 메인()
{


노드* pq = newNode(4, 1);
푸시(&pq, 5, 2);
푸시(&pq, 6, 3);
푸시(&pq, 7, 0);
// 생성된 우선순위 큐는 7 -> 4 -> 5 -> 6입니다.
동안 (!isEmpty(&pq))
{
cout << " " << 엿보기(&pq);
팝(&pq);
}
반환 0;
}

C 코드

#include <stdio.h>
#include <stdlib.h>
typedef 구조체 노드 // 노드 생성
{
정수 데이터; // 노드의 값
정수 우선 순위; // 낮은 값 = 높은 우선순위
구조체 노드* 다음; // 다음 노드에 대한 포인터

} 노드;

Node* newNode(int d, int p) // 새 노드를 생성하는 함수
{
노드* 임시 = (노드*)malloc(sizeof(노드)); // 노드의 크기 할당
임시 -> 데이터 = d; // 데이터 값 초기화
임시 -> 우선 순위 = p; // 우선순위 값 초기화
임시 -> 다음 = NULL;

반환 온도;
}

int peek(Node** head) // 헤드 노드 인쇄
{
반환 (* 헤드)-> 데이터;
}

void pop(Node** head) // 우선 순위가 가장 높은 요소 제거
{
노드* 온도 = *헤드;
(*머리) = (*머리)->다음;
무료(임시);
}

void push(Node** head, int d, int p) // 우선순위에 따라 노드를 삽입
{
노드* 시작 = (*헤드);
노드* 임시 = newNode(d, p); // 새로운 노드 생성

// 특별한 경우: 목록의 헤드는
// 새 노드보다 우선 순위가 낮습니다. 그래서
// 헤드 노드 앞에 newnode 삽입
// 헤드 노드를 변경합니다.
if ((*head)->우선순위 > p)
{

임시 -> 다음 = * 머리; // 헤드 앞에 새 노드 삽입
(* 헤드) = 온도;
}
또 다른
{


while (start->next != NULL && start->next->priority < p) // 노드에 들어갈 적절한 위치를 찾습니다.
{
시작 = 시작->다음;
}

// 목록의 끝에서
// 또는 필요한 위치에
임시 -> 다음 = 시작 -> 다음;
시작 -> 다음 = 임시;
}
}

// 확인할 함수는 목록이 비어 있는지 확인합니다.
int isEmpty(노드** 헤드)
{
반환 (* 헤드) == NULL;
}

정수 메인()
{


노드* pq = newNode(4, 1);
푸시(&pq, 5, 2);
푸시(&pq, 6, 3);
푸시(&pq, 7, 0);
// 생성된 우선순위 큐는 7 -> 4 -> 5 -> 6입니다.
동안 (!isEmpty(&pq))
{
printf("%d ", 엿보기(&pq));
팝(&pq);
}
반환 0;
}

산출:

7 4 5 6
  • 바이너리 힙: 이것은 우선순위 큐를 구현하는 가장 효율적인 방법입니다. 힙 루트 노드에서는 우선 순위가 가장 높은 요소를 사용할 수 있으며 peek 작업의 시간 복잡도는 O(1)입니다. 다음 섹션에서는 힙을 사용한 삽입 및 삭제 작업에 대해 설명합니다.

삽입과 삭제에 많은 양이 필요하기 때문에 이러한 작업에 대한 시간 복잡도는 O(log n)입니다.

CPP 코드

#include <비트/stdc++.h>
네임 스페이스 표준 사용;

정수 H[50]; // 초기 힙 크기는 50개 요소입니다.
정수 크기 = -1; // 힙에 크기가 -1인 요소가 없습니다.


int 부모(int i)
{
 
반환 (i - 1) / 2; // 주어진 노드의 부모 노드의 인덱스를 반환
}

int leftChild(int i)
{

반환 ((2 * i) + 1); // 왼쪽 자식 인덱스 반환
}


int rightChild(int i)
{

반환 ((2 * i) + 2); // 오른쪽 자식 인덱스 반환
}

// 노드를 순서대로 위로 이동하는 함수
// 힙 속성을 유지하기 위해
무효 shiftUp(int i)
{
동안 (i > 0 && H[parent(i)] < H[i]) {

// 부모 노드와 현재 노드 교체
스왑(H[부모(i)], H[i]);

// i를 i의 부모로 업데이트
나는 = 부모(i);
}
}

// 노드를 아래로 이동하는 함수
// 힙 속성을 유지하기 위해
무효 shiftDown(int i)
{
정수 maxIndex = 나;

// 왼쪽 자식
정수 l = 왼쪽 자식(i);

if (l <= 크기 && H[l] > H[maxIndex]) {
최대 인덱스 = l;
}

// 오른쪽 자식
정수 r = rightChild(i);

if (r <= 크기 && H[r] > H[maxIndex]) {
최대 인덱스 = r;
}

// maxIndex와 같지 않은 경우
if (i != maxIndex) {
스왑(H[i], H[maxIndex]);
shiftDown(최대 인덱스);
}
}

무효 삽입(int p)
{
// 이 함수는 힙에 새 요소를 추가합니다.
크기 = 크기 + 1;
H[크기] = p;

// 힙 속성을 유지하기 위해 Shift Up
shiftUp(크기);
}


정수 추출 최대()
{
정수 결과 = H[0]; // 최소 우선순위로 요소 추출

// 루트에 있는 값을 바꿉니다.
// 마지막 잎으로
H[0] = H[크기];
크기 = 크기 - 1;

// 교체된 요소를 아래로 이동
// 힙 속성을 유지하기 위해
시프트다운(0);
반환 결과;
}


무효 changePriority(int i, int p)
{
    // 요소의 우선순위 변경
int oldp = H[i];
H[i] = p;

if (p > oldp) {
shiftUp(i);
}
또 다른 {
shiftDown(i);
}
}


정수 getMax()
{

반환 H[0]; // 현재 최대 요소 가져오기
}

// 요소를 제거하는 함수
// 주어진 인덱스에 위치
무효 제거(int i)
{
H[i] = getMax() + 1;

// 노드를 루트로 이동
// 힙의
shiftUp(i);

// 노드 추출
추출맥스();
}


정수 메인()
{


삽입(1);
삽입(20);
삽입(3);
삽입(35);
삽입(31);
삽입(7);
삽입(90);
삽입(13);
삽입(9);

정수 i = 0;

// max 추출 전 우선순위 큐
cout << "우선순위 큐 : ";
동안 (i <= 크기) {
cout << H[i] << " ";
나는 ++;
}

cout << "\n";

// 최대 우선순위 노드
cout << "최대 우선순위 노드: "
<< extractMax() << "\n";

// max 추출 후 우선순위 큐
cout << "우선순위 큐"
<< "최대값 추출 : ";
정수 j = 0;
동안 (j <= 크기) {
cout << H[j] << " ";
j++;
}

cout << "\n";

// 요소의 우선 순위 변경
// 인덱스 2에서 49까지 존재
changePriority(2, 49);
cout << "우선순위 큐"
<< "우선순위 변경 : ";
정수 k = 0;
동안 (k <= 크기) {
cout << H[k] << " ";
k++;
}

cout << "\n";
// 인덱스 3의 요소 제거
제거(3);
cout << "우선순위 큐"
<< "요소 제거 : ";
정수 l = 0;
동안 (l <= 크기) {
cout << H[l] << " ";
ㄹ++;
}
반환 0;
}

산출:

우선 대기열 : 90 31 35 13 20 3 7 1 9
최대 우선순위 노드 : 90
최대 추출 후 우선순위 큐 : 35 31 9 13 20 3 7 1
우선순위 변경 후 우선순위 큐 : 49 31 35 13 20 3 7 1
요소 제거 후 우선 순위 큐 : 49 31 35 1 20 3 7
  • 정렬:
    우선 순위 대기열은 두 가지 방식으로 배열을 사용하여 구현할 수 있습니다. 정렬된 배열을 사용하는 것이 첫 번째 접근 방식이고 정렬되지 않은 배열을 사용하는 것이 두 번째 접근 방식입니다. 정렬된 배열은 우선 순위에 따라 모든 요소를 ​​포함합니다. 새 요소를 추가하려면 배열을 순회하고 순서가 유지되도록 새 요소를 삽입해야 합니다. 따라서 O(n). 삭제 및 엿보기 작업이 순서대로 수행되기 때문에 둘 다 O(1) 시간이 걸립니다.

정렬되지 않은 배열의 모든 요소가 우선 순위에 따라 정렬되지 않은 경우 배열을 정렬되지 않은 배열이라고 합니다. 따라서 요소를 삽입하는 위치는 어디에 삽입해도 상관없으므로 O(1) 시간이 걸립니다. 그러나 삭제하고 엿보기 위해서는 배열을 순회해야 하므로 최악의 경우 복잡도는 두 작업 모두에서 O(n)입니다.

CPP 코드

#include <비트/stdc++.h>
네임 스페이스 표준 사용;
struct item { // 큐에 있는 항목의 구조
정수 값; // 큐 요소의 값
정수 우선 순위; // 큐의 우선순위
};


항목 pr[100000]; // 큐의 크기

정수 크기 = -1; // 마지막 인덱스에 대한 포인터


void enqueue(int value, int priority) // 큐에 새로운 요소 삽입
{
// 크기 늘리기
크기++;

// 요소 삽입
pr[크기].값 = 값;
pr[크기].우선순위 = 우선순위;
}


int peek() // 큐의 최상위 요소 가져오기
{
int 가장 높은 우선 순위 = INT_MIN;
정수 = -1;

// 다음을 사용하여 요소를 확인합니다.
// 가장 높은 우선순위
for (int i = 0; i <= 크기; i++) {

// 우선순위가 같으면 선택
// 요소
// 가장 높은 값
if(가장 높은 우선순위
== pr[i].우선순위
&& ind > -1
&& pr[ind].값
< pr[i].값) {
가장 높은 우선순위 = pr[i].우선순위;
인드 = 나;
}
else if(가장 높은 우선순위
< pr[i].우선순위) {
가장 높은 우선순위 = pr[i].우선순위;
인드 = 나;
}
}

// 요소의 위치를 ​​반환
반환 인도;
}


무효 큐()
{
// 우선 순위가 가장 높은 요소 제거
int ind = 엿보기();

// 요소 이동
for (int i = ind; i < 크기; i++) {
pr[i] = pr[i + 1];
}

크기--; // 큐 크기 줄이기
}


정수 메인()
{
// 큐에 요소 삽입
인큐(10, 2);
인큐(14, 4);
인큐(16, 4);
인큐(12, 3);

int ind = 엿보기(); // 최상위 요소 가져오기

cout << pr[ind].값 << endl;

큐에서 빼기(); // 맨 위 요소에서 dequeue 수행

// 최상위 요소 확인
ind = 엿보기();
cout << pr[ind].값 << endl;

// 최상위 요소를 큐에서 빼냅니다.
큐에서 빼기();

// 최상위 요소 확인
ind = 엿보기();
cout << pr[ind].값 << endl;

반환 0;
}

산출:

16
14
12
  • 이진 검색 트리: 이진 검색 트리는 항목을 정렬된 순서로 효율적으로 유지하는 데 사용됩니다. 정렬 순서가 우선 순위를 기반으로 하는 경우 이진 검색 트리는 우선 순위 큐가 됩니다.

    최우선 요소를 찾는 시간 복잡도는 일정합니다. 가장 높은 우선 순위 요소는 추가 포인터에 보관할 수 있으며 삽입 및 삭제 작업이 완료되면 업데이트됩니다. inorder 후임자를 식별하면 삭제 작업으로 추가 포인터가 업데이트됩니다.

결론

우선 순위 대기열은 우선 순위가 다른 항목을 처리해야 하는 질문을 해결하는 데 중요합니다. 우선 순위 대기열은 O(1)의 시간 복잡성으로 가장 긴급한 항목에 빠르게 액세스할 수 있는 기능을 제공합니다. 우선 순위 대기열에는 느리고 대기열에 넣기 및 대기열에서 빼는 작업의 시간 복잡도가 O(log n)이라는 단점이 있습니다.

profile
Passionate about Programming, Data Science, Web Development, Full Stack Development, and curious to learn more programming stuff.

0개의 댓글