[C#]우선순위 큐와 힙

아래는 우선순위 큐의 기초적인 작성 방식이다.

 

이렇게 선언시에 클래스명에 붙이는 제네릭 형식에 우선순위가 추가된다는 점과 넣은 순서대로가 아니라 우선순위에 따라 요소가 나온다는 점만 빼면 Enqueue,Dequeue,Peek를 사용한다는 점에서 별반 다를게 없어보인다.

 

하지만 앞서 정리했던 Queue(큐) 는 PriorityQueue(우선순위 큐)와 이름은 같지만 내부적으로는 전혀 다른 구성을 갖고 있다.

 

우선 큐는 배열을 기반으로 연속적으로 데이터들을 연속적으로 일렬로 저장하며 새로운 요소가 추가될 경우 Tail에 해당하는 제일 뒤쪽에 추가하고 자료를 꺼낼 때는 Head에 해당하는 제일 앞에서 꺼내는 형식인데 우선순위 큐는 힙 트리(Heap Tree)의 구조를 갖고 있어 새로운 요소를 추가할 때는 힙 트리 구조의 제일 마지막에 요소를 추가하여 부모와 값을 비교하며 위치를 바꿔나가고, 자료를 꺼낼 때는 제일 우선순위가 높은 최상단의 요소를 꺼내는 식으로 작동한다.

그렇다면 힙은 무엇일까

 

큐의 FIFO(First In First Out) 구조

우선순위에 따라 위에서부터 2갈래로 내려가는 힙 구조

 

 

[힙 (Heap)]

 

힙은 많은 자료 중에 우선순위가 가장 높은 요소를 빠르게 가져오기 위해 사용하며 부모 노드가 항상 자식 노드보다 우선순위가 높은 속성을 만족하는 트리 기반의 자료구조이다. 

특히 불특정 다수의 자식을 가지는 것이 아닌 한 부모에 2개의 자식만을 가지는 완전 이진 트리의 형태를 가지고 있으며 최상단인 루트부터 시작하여 아래로 내려가면서 왼쪽부터 오른쪽으로 단계별로 노드가 차례로 채워져 만들어지는 구조를 가진다.이렇게 채워진 데이터들은 우선순위에 따라 정렬된 상태로 유지하면서 삭제,최소/최대값 조회 등의 연산을 빠르게 수행할 수 있다.

 

삽입과 삭제에서의 공통점은 모두 마지막에 위치한 노드에 대한 접근이 있다는 점이다.

 

먼저 최상단에 위치한 1을 꺼내거나 제거할 때를 보겠다.

 

최상단에 위치한 1의 값이 꺼내졌을 때 빈 Root 노드의 값은 Root의 왼쪽,오른쪽 자식이 아니라 최하단 제일 오른쪽에 위치한 노드의 값을 끌어 올린다.

이후 마지막 노드는 제거한다.

 

 

그 후 Root로 올려진 노드의 값은 왼쪽 오른쪽 자식과 우선순위를 비교해 자리를 바꾸는 과정을 거치는데 해당 조건을 모든 노드들이 만족할 때까지 이를 반복하게 된다.

 

 

다른 요소를 삽입할 시에도 최하단 제일 오른쪽에 해당하는 위치에 요소를 추가한 뒤, 부모와의 우선 순위의 비교를 하게 되는데 이 때도 부모보다 해당 노드의 우선 순위가 높을 경우 부모와 자리를 바꾸며 값이 올라가는 상승 작용을 거치게 된다.

 

 

이러한 힙 트리는 완전 이진 트리의 속성을 가지고 있지만 이진 검색 트리와는 다르게 각 계층이 빠짐 없이 요소들로 꽉 들어가있기 때문에 사실상 연속된 배열과 같은 상태를 띄고 있다.

따라서 요소들을 배열에 넣고 관리하여 인덱스를 통해 요소들에 접근하는 방법을 사용할 수 있는데

부모의 위치를 p라고 할 때 좌측 자식의 인덱스는 (2 * p) + 1 , 우측 자식의 인덱스는 (2 * p) + 2로 접근할 수 있고

반대로 자식의 위치를 c라고 할 때 (c - 1) / 2를 통해 접근할 수 있다.

 

 

 

그러나 C#에서 LinkedList를 잘 사용하지 않듯이 Heap 트리 또한 같은 이유로 자주 사용되는 자료구조는 아니다. 그 이유는 C#의 동적 할당과 해제의 작동 방식에서 찾을 수 있다. 

C#의 가비지 컬렉터는 메모리 관리를 자동화 하고 사용하지 않는 객체들을 정리하는 데 도움을 주는 기능을 수행한다.

 

하지만 노드 기반의 자료구조는 포인터 또는 참조로 서로 연결된 구조를 갖기 때문에 가비지 컬렉터의 잦은 호출로 불필요한 메모리 사용을 요구한다는 점이 있으며 서로 참조하는 노드들의 연결들은 순환 참조를 형성하며 이는 가비지 컬렉터가 해결하기 어려워하여 메모리 누수를 발생시킬 수 있다.

또한 많은 노드가 동적으로 생성되고 삭제될 때 가비지 컬렉터는 더 많은 부가적인 메모리 소모, 즉 오버헤드를 발생시킬 수 있다는 점 등 때문에 C#은 가비지 컬렉터와 잘 호환될 수 있는 자료 구조인 배열, 리스트, 해시테이블 등을 선호하며
이러한 가비지 컬렉터의 문제가 존재하지 않는 C++에서는 메모리를 사용자가 직접 할당하고 해제하기 때문에 위의 문제점 없이 사용할 수 있다.