우선순위 큐
이전에 알아본 큐(Queue)는 선입선출 FIFO(First In First Out)의 자료구조였다.
우선순위 큐(Priority Queue)는 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
이것을 힙(Heap)을 이용해 구현해보자.
힙은 간단히 말해 완전이진트리형태의 자료구조인데 최대값과 최소값을 빠르게 찾아낼 수 있어서 좋다.
class PriorityQueue
{
List<int> _heap = new List<int>();
public void Push(int data)
{
//맨 끝에 데이터를 삽입한다.
_heap.Add(data);
int now = _heap.Count - 1;
//도장깨기 시작
while(now > 0)
{
int next = (now-1) / 2;
//부모노드가 자식노드보다 더 크니 도장 깨기 실패
if(_heap[now] < _heap[next])
break;
//부모노드보다 자식노드가 더 크니 두 값을 교체
int temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
//다음 검사위치로 변경
now = next;
}
}
public int Pop()
{
//우선순위가 높은건 루트노드일테니 루트값 반환
int ret = _heap[0];
//마지막 데이터를 루트로 이동
int lastIndex = _heap.Count - 1;
_heap[0] = _heap[lastIndex];
_heap.RemoveAt(lastIndex);
lastIndex--;
//역으로 내려가는 도장깨기
int now = 0;
while(true)
{
int left = 2 * now + 1;
int right = 2 * now + 2;
int next = now;
///왼쪽 값이 현재값보다 크면 왼쪽으로 이동
if(left <= lastIndex && _heap[next] < _heap[left])
next = left;
//오른쪽 값이 현재값보다 크면 오른쪽으로 이동
if(right <= lastIndex && _heap[next] < _heap[right])
next = right;
// 왼쪽,오른쪽 모두 현재값보다 작으면 종료
if(next == now)
break;
//두 값을 교체
int temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
//검사 위치를 변경
next = now;
}
return ret;
}
public int Count()
{
return _heap.Count;
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue q = new PriorityQueue();
q.Push(10);
q.Push(150);
q.Push(40);
q.Push(60);
while(q.Count() > 0)
{
Console.WriteLine(q.Pop());
}
}
}
위의 코드를 실행하면 150 60 40 10 우선순위가 큰 순서대로 Pop 될 것이다.
위 코드에서 우선순위가 낮은순으로도 Pop을 할 수 있다. 코드를 바꾸지않고 - 부호를 이용하면 가능하다.
q.Push(-10);
q.Push(-150);
q.Push(-40);
q.Push(-60);
while(q.Count() > 0)
{
Console.WriteLine(-q.Pop());
}결과 값 : 10 40 60 150
위의 코드는 정수형을 넣어 정수형이 큰 순서대로 우선순위를 설정하였다면 Interface를 통하여 조금 더 일반적으로 사용할 수 있는 코드로 만들어 보자.
1.우선순위 큐를 템플릿을 이용해 일반화 해주자.
2.인터페이스 추가
3.비교문에서 정수로만 비교를 했는데 CompareTo를 통해 비교연산
//템플릿 + 인터페이스 추가
class PriorityQueue<T> where T : IComparable<T>
{
List<T> _heap = new List<T>();
public void Push(T data)
{
//맨 끝에 데이터를 삽입한다.
_heap.Add(data);
int now = _heap.Count - 1;
//도장깨기 시작
while(now > 0)
{
int next = (now-1) / 2;
//부모노드가 자식노드보다 더 크니 도장 깨기 실패
if(_heap[now].CompareTo(_heap[next]) < 0)
break;
//부모노드보다 자식노드가 더 크니 두 값을 교체
T temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
//다음 검사위치로 변경
now = next;
}
}
public T Pop()
{
//우선순위가 높은건 루트노드일테니 루트값 반환
T ret = _heap[0];
//마지막 데이터를 루트로 이동
int lastIndex = _heap.Count - 1;
_heap[0] = _heap[lastIndex];
_heap.RemoveAt(lastIndex);
lastIndex--;
//역으로 내려가는 도장깨기
int now = 0;
while(true)
{
int left = 2 * now + 1;
int right = 2 * now + 2;
int next = now;
///왼쪽 값이 현재값보다 크면 왼쪽으로 이동
if(left <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
next = left;
//오른쪽 값이 현재값보다 크면 오른쪽으로 이동
if(right <= lastIndex && _heap[next].CompareTo(_heap[right]) < 0)
next = right;
// 왼쪽,오른쪽 모두 현재값보다 작으면 종료
if(next == now)
break;
//두 값을 교체
int temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
//검사 위치를 변경
next = now;
}
return ret;
}
public int Count()
{
return _heap.Count;
}
}
class Knight : IComparable<Knight>
{
public int Id { get; set;}
//비교할수있게 인터페이스 추가
public int CompareTo(Knight other)
{
if(Id == other.Id)
return 0;
return Id > other.Id ? 1 : -1;
}
}
class Program
{
PriorityQueue<Knight> q = new PriorityQueue<Knight>();
q.Push(new Knight() { Id = 20 });
q.Push(new Knight() { Id = 40 });
q.Push(new Knight() { Id = 50 });
q.Push(new Knight() { Id = 70 });
q.Push(new Knight() { Id = 30 });
while(q.Count() > 0)
{
Console.WriteLine(q.Pop().Id);
}
}출력 결과 : 20 30 40 50 70
똑같이 잘 출력 되는것을 볼 수 있다.
오늘 알아본 내용
1. 우선순위 큐
2. 템플릿 사용 인터페이스 ICompareble
3. 인터페이스 ICompareble
Ghost