Chapter 5-2. 힙 트리 & 우선순위 큐
카테고리: Algorithm Lesson 2
인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click
Chapter 5. 트리
🚖 힙
이진 트리
이진 트리 👉 모든 노드들이 자식 노드를 최대 2 개까지만 가지는 트리
- 이진 트리의 종류
- 이진 검색 트리 (Binary Search Tree)
- 항상 왼쪽 자식은 나보다 작고 오른쪽 자식은 나보다 크다.
- 힙 트리 (Heap Tree)
- Max Heap Tree : 항상 부모가 자식보다 크다. 따라서 루트는 최대값이다.
- Min Heap Tree : 항상 부모가 자식보다 작다. 따라서 루트는 최소값이다.
- 이진 검색 트리 (Binary Search Tree)
이진 검색 트리
다음과 같은 조건이 적용된 이진트리.
- 왼쪽을 타고 가면 현재 값보다 작다. 👉 왼쪽 자식 노드는 부모 노드보다 작아야 한다.
- 루트를 기준으로 왼쪽 서브트리 노드의 데이터들은 전부 루트보다 작은 값을 가진다.
- 오른쪽을 타고 가면 현재 값보다 크다. 👉 오른쪽 자식 노드는 부모 노드보다 커야 한다.
- 루트를 기준으로 오른쪽 서브 트리 노드의 데이터들은 전부 루트보다 큰 값을 가진다.
이진 검색 트리는 이러한 구성을 가지기 때문에 해당 데이터를 가진 노드를 검색하는게 빠르다. 찾으려는 값보다 작으면 왼쪽으로 내려가고, 찾으려는 값보다 크면 오른쪽으로 내려가면 되기 때문.
- 이진 검색 트리에 값을 추가할 때
- 그냥 무식하게 추가하면 한쪽으로 기울어져서 균형이 깨진다.
- 예를 들어 트리에 있는 노드들보다 큰 값만 계속해서 추가한다면 트리가 한쪽으로만 쭉 길어질 수 있음. 이러면 리스트 같은 선형 자료구조와 다를게 없어져 이진 검색트리의 빠른 검색 이점이 사라질 수 있다.
- 👉 추가, 삭제시, 트리 재배치를 통해 균형을 유지하는 것이 과제
- 그냥 무식하게 추가하면 한쪽으로 기울어져서 균형이 깨진다.
힙 트리 ✨
다음과 같은 조건이 적용된 이진트리.
이진 검색트리보단 제약 수준이 낮다. 이진 검색트리와 달리 양쪽 자식간에는 특별한 조건이 없음.
- 힙 트리
- 조건 1️⃣
- max heap 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다. 👉 그냥 부모가 자식들보다 크면 된다.
- 이 힙 트리의 루트 값은 언제나 최대값이다.
- min heap 인 경우엔 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 작다. 👉 그냥 부모가 자식들보다 작으면 된다.
- 이 힙 트리의 루트 값은 언제나 최소값이다.
- max heap 부모 노드가 가진 값은 항상 자식 노드가 가진 값보다 크다. 👉 그냥 부모가 자식들보다 크면 된다.
- 제약 조건
- 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차있다.
- 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 한다.
- 조건 2️⃣
- 이 제약 조건 때문에 노드의 개수를 알면, 트리 구조는 무조건 확정할 수 있다.
- 만약 데이터 개수가 5 개인 경우, 힙트리 구조는 아래와 같은 구조로 확정 된다.
- 따라서 힙 구조는 데이터 개수만 알면 언제나 확정되기 때문에 배열을 이용해서 힙 구조를 바로 표현할 수 있다.
- 인덱스
i노드의 왼쪽 자식 노드의 인덱스는2 * i + 1 - 인덱스
i노드의 왼쪽 자식 노드의 인덱스는2 * i + 2 - 인덱스
i노드의 부모 노드의 인덱스는(i - 1) / 2(정수이므로 소수점 버림. 몫만.)
- 인덱스
- 이 제약 조건 때문에 노드의 개수를 알면, 트리 구조는 무조건 확정할 수 있다.
- 조건 1️⃣
힙 트리는 배열로 구현할 수 있다.
추가하기
- 조건 2️⃣ 에 의하여 👉 노드 개수를 알면 트리 구조를 무조건 확정지을 수 있으므로 우선 트리 구조부터 맞춰준다.
- 마지막 레벨에 추가하되 왼쪽에서부터 순서대로 채워넣기
- 조건 1️⃣ 에 의하여 👉 부모 노드는 항상 자식 노드보다 커야 하므로 이 조건이 만족 될 때까지 자리를 서로 뒤 바꿔 올라가게 한다.
최대값 꺼내기(루트 삭제하기)
- 최대값을 먼저 제거한다. 👉 힙 트리 모양이 망가지므로 다시 재정비 해주어야 한다.
- 조건 2️⃣ 에 의하여 제일 마지막에 위치한 데이터를 빈 루트 자리로 옮긴다.
- 조건 1️⃣ 에 의하여 👉 부모 노드는 항상 자식 노드보다 커야 하므로 이 조건이 만족 될 때까지 자리를 서로 뒤 바꿔 내려가게 한다.
🚖 우선순위 큐 구현
using System;
using System.Collections.Generic;
namespace Excercise
{
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;
// 검사 위치로 이동한다.
now = next;
}
return ret;
}
public int Count()
{
return _heap.Count;
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue q = new PriorityQueue();
q.Push(20);
q.Push(10);
q.Push(30);
q.Push(90);
q.Push(40);
while (q.Count() > 0) // 90 40 30 20 10 출력
{
Console.WriteLine(q.Pop());
}
}
}
}
우선순위 큐 자료구조는 힙 트리를 사용한다.
우선순위 큐- 들어간지 가장 오래된게 나오는 선입선출 방식인 일반 큐와 달리, 들어간 순서와는 상관없이 가장 큰 값을 가진 데이터가 빠져나오게 된다.
- 👉
Max Heap Tree를 우선순위 큐 자료구조로서 사용하면 된다.- 루트 노드는 언제나 최대값이 오도록 힙 트리 구조 유지.
- 데이터를 뽑을 땐 루트 노드 데이터를 뽑으면 됨.
- Min Heap 은
Max Heap Tree로 구현된 우선순위 큐에 원하는 데이터들을-붙여 음수로 넣은 후 꺼내고 나서 다시-을 붙여 원래대로 양수로 만들어 사용할 수도 있다.- 음수는 절대값이 작은게 큰 것이라는 점을 이용하여.
- 👉
- 들어간지 가장 오래된게 나오는 선입선출 방식인 일반 큐와 달리, 들어간 순서와는 상관없이 가장 큰 값을 가진 데이터가 빠져나오게 된다.
- 힙 트리는 배열로 나타낼 수 있다.
List<int> _heap = new List<int>();
Push : 우선순위 큐에 노드 추가
힙 트리의 추가 과정 그림 위에서 참고!
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;
}
}
삽입은 아래에서 부터 위로 올라가며 스왑해나간다.
- 새로운 데이터는 힙의 맨 끝에 삽입한다.
- 힙 트리는 배열로 관리되므로 배열에 추가하면 된다.
now에는 처음에 추가한 데이터의 바뀌어 가는 인덱스_heap.Count - 1에서 시작
- 부모 > 자식 관계가 완성될 때까지 위로 올라가며 추가한 데이터를 스왑해 나간다. 제자리를 찾기 위한 과정
next는 현재의now의 부모- _heap[now] < _heap[next]
- 힙 트리 조건(부모 > 자식)을 만족하는 제 자리를 찾았으니 끝냄
- _heap[now] >= _heap[next]
- 자식이 부모보다 더 크므로 안된다. 제 자리를 찾아 올라가야 하므로 둘이 스왑한다.
- 스왑한 후
- 위로 올라간다.
now = next
- 자식이 부모보다 더 크므로 안된다. 제 자리를 찾아 올라가야 하므로 둘이 스왑한다.
Pop : 우선순위 큐에서 최대값 뽑기 👉 루트 노드 삭제
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;
// 검사 위치로 이동한다.
now = next;
}
return ret;
}
힙 트리의 루트 노드는 늘 최대값이다. 모든 부모 노드는 자식 노드들보다 크기 때문이다.
루트 노드 삭제 및 리턴인 Pop 은 아래로 내려가며 스왑해나간다.
- 루트 노드
_heap[0]를 리턴해야 하니까 삭제 전에ret에 보존해두기- 나중에 이를 리턴하고 끝낸다.
- 마지막 데이터를 빈 루트 노드 자리로 이동시킨다.
- 루트 노드에 마지막 노드 복사
- 마지막 노드 삭제
lastIndex는 힙 트리의 마지막 인덱스now는 루트 노드에 올라오게 된 마지막 데이터가 제 자리를 찾아가는 과정마다 위치하게 될 인덱스를 저장- 루트에서 시작하므로 0 에서 시작
next에 다음에 내려갈 위치- 현재
now의 왼쪽 자식left - 현재
now의 오른쪽 자식right - 루트에 올라오게 된 마지막 데이터를 부모 > 자식 관계가 완성될 때까지 아래로 내려가며 스왑해 나간다. 제자리를 찾기 위한 과정
- 인덱스를 넘지 않기 위해
left,right가lastIndex보다 작은지를 검사 - 왼쪽 자식이 더 크다면
next를left로 업데이트 - 오른쪽 자식이 더 크다면
next를right로 업데이트- 왼쪽 자식보다 오른쪽 자식이 더 크다면
next는 오른쪽 자식으로 또 업데이트 된다. - else if 가 아닌 그냥 if 이기 때문에
- 왼쪽 자식보다 오른쪽 자식이 더 크다면
- 인덱스를 넘지 않기 위해
next가 업데이트 되지 않아 여전히now라면 왼쪽 자식 오른쪽 자식 둘 다 현재 값보다 작다는 의미이므로 제자리를 찾았으니 저장해두었던 예전 루트 노드ret을 리턴하고 종료.- 스왑한 후 아래로 내려간다.
now = next
힙 트리(우선순위 큐)의 추가/삭제 연산은 \(O(logN)\) 시간 복잡도를 가진다. 즉, 트리의 높이에 따라 시간 복잡도가 결정 된다. 타고 내려가고 타고 올라가기 때문에.
Count
public int Count()
{
return _heap.Count;
}
우선순위 큐의 데이터 노드 개수는 힙 배열의 크기와 같음.
🚖 제네릭한 우선순위 큐 구현
using System;
using System.Collections.Generic;
namespace Excercise
{
class Knight : IComparable<Knight>
{
public int id { get; set; }
public int CompareTo(Knight other)
{
// id 멤버를 기준으로 크기를 비교
if (id == other.id)
return 0;
return id > other.id ? 1 : -1;
}
}
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;
// 두 값 서로 자리 바꿈
T temp = _heap[now];
_heap[now] = _heap[next];
_heap[next] = temp;
// 검사 위치로 이동한다.
now = next;
}
return ret;
}
public int Count()
{
return _heap.Count;
}
}
class Program
{
static void Main(string[] args)
{
PriorityQueue<Knight> q = new PriorityQueue<Knight>();
q.Push(new Knight() { id = 20 });
q.Push(new Knight() { id = 10 });
q.Push(new Knight() { id = 30 });
q.Push(new Knight() { id = 90 });
q.Push(new Knight() { id = 40 });
while (q.Count() > 0) // 90 40 30 20 10 출력
{
Console.WriteLine(q.Pop());
}
}
}
}
IComparable<T> 인터페이스를 상속 받으면 CompareTo 비교 함수를 구현해야 한다. int 같은 기본 데이터 타입이 아닌 사용자 정의 객체 타입이라면 비교할 기준을 따로 마련해 주어야 우선순위 큐에 넣을 수 있다. (우선 순위 큐 자체가 비교와 비교를 거듭하여 항상 부모 > 자식 관계를 유지하게 하는 자료구조이므로)
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글 남기기