우선순위 큐

우선순위 큐 (Priority Queue)

우선순위 큐는 특정 조건에 따라 우선순위를 부여하여 데이터를 저장하는 데이터 구조입니다. 주로 힙(Heap)을 사용하여 구현되며, 최소 우선순위 큐와 최대 우선순위 큐가 있습니다. 이 데이터 구조는 Dijkstra 알고리즘, A* 탐색 알고리즘 등에서 사용됩니다.

C

• C에서 우선순위 큐를 구현할 때는 보통 배열, 연결 리스트, 또는 힙을 사용합니다.
• 표준 라이브러리에서는 <queue> 헤더에 priority_queue를 제공하지만, 이것은 C++의 일부입니다.
• 수동으로 메모리 관리를 해야 하며, 동적 메모리 할당과 해제를 신경 써야 합니다.

#include <stdio.h>
#include <stdlib.h>

// A simple max heap example in C
typedef struct {
    int *data;
    int size;
    int capacity;
} MaxHeap;

void push(MaxHeap *heap, int val) {
    // ... push logic here
}

int pop(MaxHeap *heap) {
    // ... pop logic here
    return 0; // Placeholder
}

int main() {
    MaxHeap heap;
    // ... initialize and use the heap
    return 0;
}

Python

• Python에서는 표준 라이브러리인 heapq 모듈을 사용하여 우선순위 큐를 쉽게 구현할 수 있습니다.
• Python의 heapq는 최소 힙만을 지원하기 때문에 최대 힙을 사용하려면 부호를 반대로 취해야 합니다.
• 메모리 관리가 자동으로 이루어지며, 구현이 훨씬 간결합니다.

import heapq

# Using heapq module in Python
min_heap = []
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 1)
heapq.heappush(min_heap, 4)

# Pop the smallest element
smallest = heapq.heappop(min_heap)

요약

• C에서는 성능 최적화와 메모리 관리가 가능하지만, 구현이 복잡하고 표준 라이브러리의 지원이 제한적입니다.
• Python에서는 간단한 구현과 높은 수준의 표준 라이브러리 지원이 있지만, 실행 속도가 C보다 느릴 수 있습니다.
• 두 언어 모두 우선순위 큐를 구현할 수 있으나, 어떤 측면을 중요하게 생각하는지에 따라 적절한 언어를 선택할 수 있습니다.