C++의 DsPriorityQueue 클래스는 우선순위 큐를 구현하기 위해 사용할 수 있습니다. 우선순위 큐는 우선순위가 가장 높은 원소를 제거하고 반환하는 것을 목표로 합니다.
우선순위가 동일한 원소가 여러 개 있는 경우, pop 메서드는 일반적으로 최소 힙 또는 최대 힙을 사용하여 구현됩니다. 최소 힙에서는 우선순위가 가장 낮은 원소를 제거하고 반환합니다. 최대 힙에서는 우선순위가 가장 높은 원소를 제거하고 반환합니다.
DsPriorityQueue 클래스는 일반적으로 최소 힙을 사용하여 구현됩니다. 따라서 우선순위가 동일한 원소가 여러 개 있는 경우, pop 메서드는 첫 번째 원소를 반환하고 제거합니다.
예를 들어, 우선순위가 동일한 원소가 여러 개 있는 경우 다음과 같은 상황이 발생할 수 있습니다.
- 원소 1: 우선순위 5
- 원소 2: 우선순위 5
- 원소 3: 우선순위 3
이 경우, pop 메서드는 우선순위가 가장 낮은 원소를 제거하고 반환합니다. 따라서 첫 번째 원소인 원소 3가 제거되고 반환됩니다.
#hostingforum.kr
cpp
#include
#include
class DsPriorityQueue {
public:
void push(int priority, int value) {
elements.push_back({priority, value});
heapifyUp(elements.size() - 1);
}
int pop() {
if (elements.empty()) {
return -1; // 또는 예외를 발생시킵니다.
}
if (elements.size() == 1) {
int result = elements[0].second;
elements.pop_back();
return result;
}
int result = elements[0].second;
elements[0] = elements.back();
elements.pop_back();
heapifyDown(0);
return result;
}
private:
struct Element {
int priority;
int value;
};
std::vector elements;
void heapifyUp(int index) {
if (index == 0) {
return;
}
int parentIndex = (index - 1) / 2;
if (elements[parentIndex].priority > elements[index].priority) {
std::swap(elements[parentIndex], elements[index]);
heapifyUp(parentIndex);
}
}
void heapifyDown(int index) {
int leftChildIndex = 2 * index + 1;
int rightChildIndex = 2 * index + 2;
int smallestIndex = index;
if (leftChildIndex < elements.size() && elements[leftChildIndex].priority < elements[smallestIndex].priority) {
smallestIndex = leftChildIndex;
}
if (rightChildIndex < elements.size() && elements[rightChildIndex].priority < elements[smallestIndex].priority) {
smallestIndex = rightChildIndex;
}
if (smallestIndex != index) {
std::swap(elements[index], elements[smallestIndex]);
heapifyDown(smallestIndex);
}
}
};
int main() {
DsPriorityQueue pq;
pq.push(5, 1);
pq.push(5, 2);
pq.push(3, 3);
int result = pq.pop();
std::cout << "Pop: " << result << std::endl;
return 0;
}
이 예제 코드에서는 DsPriorityQueue 클래스를 구현하고 우선순위가 동일한 원소가 여러 개 있는 경우 pop 메서드의 동작을 보여줍니다.
2025-05-19 09:47