데이터 구조의 우선 순위 큐: 특성, 유형 및 구현

소개

데이터 구조 의 우선 순위 큐 는 "일반" 큐의 확장입니다. 항목 그룹을 포함하는 추상 데이터 유형입니다. 대기열에서 빼는 요소가 우선 순위를 따른다는 점을 제외하고는 "일반" 대기열과 같습니다. 우선 순위는 우선 순위가 가장 높은 항목을 먼저 대기열에서 뺍니다. 이 블로그는 우선순위 큐와 C 프로그래밍 언어에서의 구현에 대한 더 깊은 이해를 제공합니다.

우선 순위 대기열이란 무엇입니까?

데이터 세트를 유지 관리하는 방법을 제공하는 추상 데이터 유형입니다. "일반" 대기열은 선입 선출의 패턴을 따릅니다. 삽입 작업과 동일한 순서로 요소를 큐에서 빼냅니다. 그러나 우선 순위 대기열의 요소 순서는 해당 대기열의 요소 우선 순위에 따라 다릅니다. 우선 순위 큐는 우선 순위 큐의 시작 부분에서 가장 높은 우선 순위 요소를 이동하고 우선 순위 큐의 뒤쪽에서 가장 낮은 우선 순위 요소를 이동합니다.

비교할 수 있는 요소만 지원합니다. 따라서 데이터 구조 의 우선 순위 큐 는 요소를 오름차순 또는 내림차순으로 정렬합니다.

우선순위 대기열은 병원에서 줄을 서서 기다리는 여러 환자로 생각할 수 있습니다. 여기서 환자의 상황에 따라 우선순위가 결정됩니다. 가장 심각한 부상을 입은 환자가 대기열의 첫 번째 환자가 됩니다.

우선순위 큐의 특징은 무엇입니까?

대기열은 다음과 같은 특성을 갖는 경우 우선 순위 대기열이라고 합니다.

• 각 항목에는 관련된 우선 순위가 있습니다.
• 우선 순위가 가장 높은 항목이 맨 앞으로 이동하여 먼저 삭제됩니다.
• 두 요소가 동일한 우선 순위 값을 공유하는 경우 우선 순위 대기열은 대기열에서 제거 작업에 대한 선입선출 원칙을 따릅니다.

우선 순위 대기열의 유형은 무엇입니까?

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

• 오름차순 우선 순위 대기열
• 내림차순 우선 순위 큐

오름차순 우선 순위 대기열

오름차순 우선 순위 대기열은 해당 대기열의 낮은 번호에 가장 높은 우선 순위를 부여합니다. 예를 들어, 우선순위 대기열에 4, 8, 12, 45, 35, 20인 6개의 숫자가 있다고 가정합니다. 먼저 이 숫자를 오름차순으로 정렬합니다. 새 목록은 다음과 같습니다. 4, 8, 12, 20. 35, 45. 이 목록에서 4가 가장 작은 숫자입니다. 따라서 오름차순 우선 순위 대기열은 4번을 가장 높은 우선 순위로 처리합니다.

위의 표에서 4가 가장 높은 우선 순위를 가지며 45가 가장 낮은 우선 순위를 갖습니다.

내림차순 우선 순위 큐

내림차순 우선 순위 대기열은 해당 대기열에서 가장 높은 번호에 가장 높은 우선 순위를 부여합니다. 예를 들어, 우선순위 대기열에 4, 8, 12, 45, 35, 20인 6개의 숫자가 있다고 가정합니다. 먼저 이 숫자를 오름차순으로 정렬합니다. 새 목록은 45, 35, 20, 12, 8, 4입니다. 이 목록에서 45가 가장 높은 숫자입니다. 따라서 내림차순 우선 순위 대기열은 45번을 가장 높은 우선 순위로 처리합니다.

위의 표에서 4가 가장 낮은 우선 순위를 가지며 45가 가장 높은 우선 순위를 갖습니다.

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

다음 방법 중 하나로 우선 순위 대기열을 구현할 수 있습니다.

• 연결 목록
• 바이너리 힙
• 배열
• 이진 검색 트리

바이너리 힙은 데이터 구조 에서 우선순위 큐 를 구현하는 가장 효율적인 방법입니다 .

아래 표는 우선 순위 대기열에서 다양한 작업의 복잡성을 요약합니다.

바이너리 힙

이진 힙 트리는 트리의 모든 상위 및 하위 노드를 특정 순서로 구성합니다. 바이너리 힙 트리에서 부모 노드는 최대 2개의 자식 노드를 가질 수 있습니다. 상위 노드의 값은 다음 중 하나일 수 있습니다.

• 자식 노드의 값과 같거나 작습니다.
• 자식 노드의 값 이상입니다.

위의 프로세스는 바이너리 힙을 최대 힙과 최소 힙의 두 가지 유형으로 나눕니다.

최대 힙

최대 힙은 부모 노드가 자식 노드 값보다 크거나 같은 값을 갖는 바이너리 힙입니다. 트리의 루트 노드가 가장 높은 값을 갖습니다.

최대 힙 이진 트리에 요소 삽입

다음 단계를 수행 하여 데이터 구조의 우선 순위 대기열에 요소/번호를 삽입할 수 있습니다 .

1. 알고리즘은 트리를 위에서 아래로, 왼쪽에서 오른쪽으로 스캔하여 빈 슬롯을 찾습니다. 그런 다음 트리의 마지막 노드에 요소를 삽입합니다.
2. 요소를 삽입한 후 이진 트리의 순서가 흐트러집니다. 최대 힙 이진 트리의 순서를 정렬하려면 데이터를 서로 교환해야 합니다. 트리가 max-heap 속성을 만족할 때까지 데이터를 계속 섞어야 합니다.

최대 힙 이진 트리에 요소를 삽입하는 알고리즘

트리가 비어 있고 노드가 없으면

새 부모 노드 newElement를 만듭니다.

else(부모 노드는 이미 사용 가능)

트리의 끝에 newElement를 삽입합니다(즉, 트리의 마지막 노드 왼쪽에서 오른쪽으로).

나무를 최대화하다

최대 힙 이진 트리에서 요소 삭제

1. 다음 단계를 수행하여 데이터 구조의 우선 순위 대기열에 있는 요소를 삭제할 수 있습니다 .
2. 이진 트리에서 삭제할 요소를 선택합니다.
3. 마지막 노드 데이터와 교환하여 트리 끝의 데이터를 이동합니다.
4. 이진 트리의 마지막 요소를 제거합니다.
5. 요소를 삭제하면 이진 트리의 순서가 깨집니다. max-heap 속성을 만족하도록 순서를 정렬해야 합니다. 트리가 max-heap 속성을 충족할 때까지 데이터를 계속 섞어야 합니다.

최대 힙 이진 트리에서 요소를 삭제하는 알고리즘

elementUpForDeletion이 lastNode인 경우

elementUpForDeletion 삭제

그렇지 않으면 elementUpForDeletion을 lastNode로 바꿉니다.

elementUpForDeletion 삭제

나무를 최대화하다

최대 힙 이진 트리에서 최대 또는 최소 요소 찾기

최대 힙 이진 트리에서 찾기 작업은 트리의 상위 노드(가장 높은 요소)를 반환합니다.

최대 힙 이진 트리에서 최대 또는 최소를 찾는 알고리즘

부모 노드 반환

Max Heap Binary Tree를 이용한 Priority Queue의 프로그램 구현

최소 힙

min-heap은 부모 노드의 값이 자식 노드 값 이하인 바이너리 힙입니다. 트리의 루트 노드는 가장 낮은 값을 갖습니다.

순서를 반대로 하는 것을 제외하고는 최대 힙과 동일한 방식으로 최소 힙을 구현할 수 있습니다.

결론

기사에 제공된 예는 설명을 위한 것입니다. 요구 사항에 따라 위에 제공된 설명을 수정할 수 있습니다. 이 블로그에서 우리 는 데이터 구조에서 우선순위 큐 의 개념에 대해 배웠습니다 . 예제를 시도하여 데이터 구조 지식을 강화할 수 있습니다.

데이터 과학에 대해 자세히 알고 싶으시면 작업 전문가를 위해 만들어졌으며 10개 이상의 사례 연구 및 프로젝트, 실용적인 실습 워크샵, 업계 전문가와의 멘토링, 1 - 업계 멘토와 일대일, 400시간 이상의 학습 및 최고의 기업과의 취업 지원.

세계 최고의 대학에서 온라인으로 데이터 과학 과정 을 배우십시오 . 이그 제 큐 티브 PG 프로그램, 고급 인증 프로그램 또는 석사 프로그램을 획득하여 경력을 빠르게 추적하십시오.