인트로
본 포스팅을 이해하기 위해선 힙 자료구조 배경지식이 필요합니다.
본 포스팅은 1)우선순위 큐 설명 2)우선순위 큐와 힙의 관계 3)구현 코드로 구성되어 있습니다.
우선순위 큐란?
큐(Queue)란 먼저 들어간 데이터가 먼저 나오는 선입 선출(First In First Out, FIFO) 구조의 자료구조를 말한다.
우선순위 큐(Priority Queue)는 일반 큐와 이름은 비슷하지만 동작하는 방식이 다르다. 우선순위 큐의 각 원소(데이터)는 저마다의 우선순위를 가지고 있으며 들어간 순서에 상관없이 높은 우선순위를 가진 원소가 순서대로 나온다는 특징이 있다.
우선순위 큐와 힙 (우선순위 큐 ≠ 힙)
당신에게 음료수 자판기를 만들라는 과제가 주어졌다. 당신은 자판기를 만들기 위한 고민을 하기 시작할 텐데 가장 먼저 할 수 있는 일은 동전 투입구에 돈을 넣으면 잔액이 충전된다, 버튼을 누르면 음료가 나온다, 잔돈을 거스른다 등 자판기라면 갖춰야 할 기능을 정리해 나갈 것이다. 그리고 어느 정도 정리가 끝나면 실제 제작과 관련해서 음료가 나오는 통로는 어떻게 설계할지, 내부 소재는 무엇을 사용할지 등을 고민할 것이다.
그럼 다시 우선순위 큐로 돌아와서, 우선순위 큐는 자료구조의 동작 방식과 인터페이스만 명시할 뿐 구현과는 아무런 관계가 없다. 실제 구현은 힙이나 배열 또는 연결 리스트로 구현한다. 단지 힙을 사용했을 때 우선순위 큐의 성능이 가장 좋기에 우선순위 큐를 힙으로 구현할 뿐이지 배열이나 연결 리스트로도 구현이 가능하다.
결국 앞서 말한 자판기가 곧 우선순위 큐이다.
자판기는 동전을 넣고 버튼을 누르면 음료가 나오는 기계 그 이상도 이하도 아니다. 내부적으로 어떻게 설계했던 무슨 소재를 썼던 그저 동전을 넣고 버튼을 눌렀을 때 음료수가 나온다면 우리는 그것을 자판기라 부른다.
우선순위 큐는 높은 우선순위의 원소가 먼저 나오는 추상 자료형 그 이상도 이하도 아니다. 내부적으로 어떻게 원소를 관리하던 그저 enqueue, dequeue 인터페이스를 호출했을 때 정상적으로 원소가 삽입되고 가장 높은 우선순위의 원소가 나온다면 그게 곧 우선순위 큐라는 것이다.
다만 앞서 말한 대로 구현 방식에 따라 성능이 달라질 수 있으며 우선순위 큐는 힙으로 구현하는 것이 가장 좋은 효율을 보일 뿐 우선순위 큐는 절대 힙이 아니다.
참고로 힙은 배열 또는 리스트로 구현하는 것이 일반적이다.
여기서 헷갈리면 안되는 게 우선순위 큐를 배열로 구현하는 것과 배열로 구현된 힙으로 우선순위 큐를 구현하는 것은 전혀 다르다. 헷갈릴 수 있으니 예제를 보자.
우선순위 큐 : 리스트로 구현 (C#)
코드를 살펴보면 우선순위 큐를 배열 또는 리스트로 구현했을 때 생기는 고질적인 문제가 드러난다.
Enqueue는 상수 시간O(1)에 처리되지만 Dequeue는 선형 시간O(N)을 소요한다. 이유는 우선순위가 높은 원소를 찾고 원소들을 앞으로 밀어 넣는 작업 때문에 발생한다.
참고 사진과 링크
(+ 사실 List를 사용하면 Value를 찾고 Remove를 바로 때려도 되지만 이해를 위해 돕기 위해 앞으로 밀어 넣고 RemoveAt을 호출했다.)
using System;
using System.Collections.Generic;
namespace PriorityQueue
{
class Item
{
public int Value { get; set; }
public int Priority { get; set; }
}
class PriorityQueue
{
private const int MIN_PRI = -1;
private List<Item> _items;
public int PeekValue { get { return _items[GetPeekIdx()].Value; } }
public PriorityQueue()
{
_items = new List<Item>();
}
public bool Enqueue(int value, int priority)
{
_items.Add(new Item() { Value = value, Priority = priority });
return true;
}
public void Dequeue()
{
int idx = GetPeekIdx();
for (int i = idx; i < _items.Count - 1; i++)
_items[i] = _items[i + 1];
_items.RemoveAt(_items.Count - 1);
}
public int GetPeekIdx()
{
int highestPriority = MIN_PRI;
int idx = 0;
for (int i = 0; i < _items.Count; i++)
{
if (highestPriority == _items[i].Priority &&
_items[idx].Value > _items[i].Value)
{
highestPriority = _items[i].Priority;
idx = i;
}
else if (highestPriority < _items[i].Priority)
{
highestPriority = _items[i].Priority;
idx = i;
}
}
// 우선순위가 가장 높은 원소 반환
return idx;
}
public void ShowItems()
{
Console.WriteLine("====================");
Console.WriteLine("Priority Queue Items");
for (int i = 0; i < _items.Count; i++)
{
Console.Write("Priority : ");
Console.Write(_items[i].Priority);
Console.Write(" Value : ");
Console.WriteLine(_items[i].Value);
}
Console.WriteLine("====================");
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue prq = new PriorityQueue();
prq.Enqueue(10, 5);
prq.Enqueue(15, 3);
prq.Enqueue(20, 1);
prq.Enqueue(5, 10);
prq.Enqueue(30, 7);
prq.ShowItems();
Console.WriteLine("Peek value : " + prq.PeekValue);
prq.Dequeue();
prq.ShowItems();
Console.WriteLine("Peek value : " + prq.PeekValue);
}
}
}
우선순위 큐 : 힙으로 구현 (C#)
힙으로 구현한 우선순위 큐는 Enqueue와 Dequeue 모두 O(logN)의 시간 복잡도를 가진다.
그 이유는 간단하다. 삽입과 삭제 모두 트리의 높이만큼 타고 올라가는데 힙은 완전 이진 트리로 그 높이가 logN이다.
using System;
using System.Collections.Generic;
namespace PriorityQueue
{
class Item
{
public int Value { get; set; }
public int Priority { get; set; }
}
class PriorityQueue
{
private List<Item> _heap = new List<Item>();
public void Enqueue(int priority, int value)
{
_heap.Add(new Item() { Priority = priority, Value = value });
int now = _heap.Count - 1;
while (now > 0)
{
int next = (now - 1) / 2;
if (_heap[now].Priority < _heap[next].Priority)
break;
Item temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
now = next;
}
}
public Item Dequeue()
{
Item ret = _heap[0];
int lastIdx = _heap.Count - 1;
_heap[0] = _heap[lastIdx];
_heap.RemoveAt(lastIdx);
lastIdx--;
int now = 0;
while (true)
{
int left = 2 * now + 1;
int right = 2 * now + 2;
int next = now;
if (left <= lastIdx && _heap[next].Priority < _heap[left].Priority)
next = left;
if (right <= lastIdx && _heap[next].Priority < _heap[right].Priority)
next = right;
if (now == next)
break;
Item temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
now = next;
}
return ret;
}
public void ShowItems()
{
Console.WriteLine("====================");
Console.WriteLine("Priority Queue Items");
for (int i = 0; i < _heap.Count; i++)
Console.WriteLine($"Priority : {_heap[i].Priority} Value : {_heap[i].Value}");
Console.WriteLine("====================");
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue prq = new PriorityQueue();
prq.Enqueue(5, 10);
prq.Enqueue(2, 100);
prq.Enqueue(10, 90);
prq.Enqueue(1, 2);
prq.Enqueue(20, 200);
prq.ShowItems();
Item it = prq.Dequeue();
Console.WriteLine($"Dequeued Priority : {it.Priority} Value : {it.Value}");
prq.ShowItems();
}
}
}
'Data structure' 카테고리의 다른 글
| [Data Structure] 트리(Tree)와 그래프(Graph) 이해하기 (0) | 2021.08.16 |
|---|