C++의 힙 및 우선순위 큐

힙과 우선순위 큐는 C++에서 일반적으로 사용되는 데이터 구조이며 둘 다 중요한 애플리케이션 가치를 가지고 있습니다. 이 기사에서는 독자가 힙과 우선순위 큐를 더 잘 이해하고 사용할 수 있도록 각각 소개하고 분석합니다.

1. 힙

힙은 우선순위 큐를 구현하는 데 사용할 수 있는 특별한 트리 데이터 구조입니다. 힙에서 각 노드는 다음 속성을 충족합니다.

1. 해당 값은 상위 노드 값보다 작거나 크지 않습니다.
2. 왼쪽 및 오른쪽 하위 트리도 힙입니다.

부모 노드보다 작지 않은 힙을 "최소 힙"이라고 하고 부모 노드보다 크지 않은 힙을 "최대 힙"이라고 합니다. 또한 힙은 일반적으로 완전한 이진 트리입니다. 즉, 노드가 왼쪽에서 오른쪽으로 배열되는 마지막 수준을 제외하고 다른 수준의 노드는 가득 차 있습니다.

C++에서 STL 라이브러리는 힙을 구현하기 위해 힙과 Priority_queue라는 두 가지 클래스를 제공합니다. 그 중 힙 클래스는 make_heap, push_heap, pop_heap 등의 힙 연산 기능을 제공하고, 우선순위_큐 클래스는 힙 구현을 기반으로 한 우선순위 큐이다. 다음으로 heap과 Priority_queue의 사용법을 살펴보겠습니다.

1. 힙 클래스

(1) 힙 만들기

힙을 만들기 전에 정렬할 숫자를 저장할 벡터 유형 배열을 만들어야 합니다.

Vector v = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3 };

그런 다음 make_heap 함수를 사용하여 벡터 유형 배열을 힙으로 변환할 수 있습니다.

make_heap(v.begin(), v.end (), Greater());

그 중 Greater()는 힙의 종류를 제어할 수 있는 비교 함수를 나타냅니다.

(2) 요소 삽입

힙에 요소를 삽입하려면 push_heap 함수를 사용할 수 있습니다. 사용법은 다음과 같습니다.

v.push_back(7);
push_heap(v.begin(), v.end (), great());

(3) 요소 삭제

힙에서 요소를 삭제하려면 pop_heap 함수를 사용하면 힙의 맨 위 요소가 힙의 마지막 위치로 이동됩니다. 힙에서 요소를 삭제합니다. 이 함수의 사용법은 다음과 같습니다:

pop_heap(v.begin(), v.end(), 더 큰());
v.pop_back();

2. priority_queue class

(1 ) 힙 생성

힙 클래스와 달리 Priority_queue 클래스는 객체 선언 시 다음과 같이 힙 유형을 지정할 수 있습니다. 최소 힙을 생성하는 것을 의미합니다.

(2) 요소 삽입

priority_queue에 요소를 삽입하면 아래와 같이 푸시 기능을 직접 사용할 수 있습니다.

q.pop();

2. 우선순위 큐는 우선순위에 따라 요소를 정렬하여 우선순위가 가장 높은 요소를 큐의 맨 앞에 배치하고 우선순위가 가장 낮은 요소를 큐의 끝에 배치하는 특수 큐입니다. 힙을 사용하여 우선순위 큐를 구현할 수 있습니다.

C++에서 Priority_queue 클래스는 힙을 기반으로 구현된 우선순위 큐이며, 위 힙 및 Priority_queue 클래스의 함수를 사용하여 요소 삽입 및 삭제 작업을 수행할 수 있습니다. 또한 top 함수는 다음과 같이 우선순위가 가장 높은 요소에 액세스하는 데 사용되는 Priority_queue 클래스에도 제공됩니다.

priority_queue q;

q.push (4);

q.push(9);

위 내용은 C++의 힙 및 우선순위 큐의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!