자료구조 (9), Priority Queue

자료구조 (9), Priority Queue

2022. 6. 21. 00:21ㆍ강의 내용 정리/자료구조

728x90

Heap

1. Heap

1) Heap이란?

- Heap은 Priority Queue와 밀접한 관계가 있다. Priority Queue 내부에 Heap을 사용하는 경우가 많다. 힙은 노드에는 우선순위에 관한 자료를 추가적으로 가지고 있다.

- 힙은 이진트리이지만 BST는 아니다. BST는 크기의 대소 관계에 따라 데이터를 삽입한다.

- 이진트리는 자식이 최대 두개까지 있는 것을 의미한다. 또한 가장 깊은 노드에 있는 것을 제외한 노드는 모두 2개의 자식이 있고, 가장 하단에 있는 노드는 좌하단부터 노드를 채워간다. 최대힙은 모든 노드는 자기의 자식보다 더 크거나 같은 트리를 가지게 된다. 따라서 루트에 있는 값만 확인하면 된다.

- 왼쪽의 예시는 힙은 아니지만 오른쪽은 최대힙이다.

2) Heap의 특징

- 힙은 리프 노드를 제외한 노드들은 모두 자식을 둘 씩 가지고 있고, 좌측부터 노드가 채워지는 partially complete binary tree이다. 또한 최대힙의 경우 자식보다 더 크거나 같은 값을 가진다는 특징이 있다.

- 힙은 랜덤 액세스가 가능한 어레이 형태로 구현하는 경우가 많다. 또한 Complete binary tree이기에 삽입할 때 손해보는 것을 방지한다. 반면 트리는 포인터를 통해 구현하기도 한다.

- 자식에 접근하기 위해서는 좌측 자식의 경우에는 '(본인 노드의 인덱스 x 2) + 1'의 인덱스를 계산해서 구하면 된다. 우측 자식의 경우에는 '(본인 노드의 인덱스 x 2) + 2'를 하면 된다. 부모에 접근하기 위해서는 '(본인 노드의 인덱스 - 1) / 2'를 하면 된다. 이때 정수 연산이기에 소수점은 버려진다. 이는 이진트리의 구조가 유지되기 때문에 그렇다. 링크드 구조는 부모 노드에 들어가기 어렵지만 이는 부모에 대한 접근이 쉽다는 장점이 있다.

3) Heap구조를 유지하기 위한 주요한 메소드

(1) ReHeapDown

- 루트를 제거된 상황에서 힙구조를 유지하기 위해 사용하는 멤버 함수로 가장 최하단의 우측에 있는 노드를 루트노드로 올리고 자식들 중에 자기보다 더 큰 값이 있다면 위치를 바꿔주는 과정을 거친다. 이때 자식 노드를 비교한 뒤 그 중 더 큰 값과 비교를 한다. 따라서 비교 연산이 두 번 등장한다. 이는 리프에 도달하거나 자식보다 자신이 더 클 때까지 반복한다. 이는 재귀적으로 호출된다. 최하단의 우측에 있는 노드를 루트노드로 올리는 이유는 Complete binary tree를 만족시키기 위해 올리는 것이다. 만약 좌측, 우측의 값을 올린다면 어레이 형태이기에 더 많은 동작을 수반해야하고 어떤 값이 더 큰지 파악하기도 어렵다.

(2) ReHeapUp

- 데이터를 삽입할 때 상황에서 힙구조를 유지하기 위해 사용하는 멤버 함수로 가장 최하단의 우측에 노드를 삽입한 뒤, 본인과 부모 노드를 비교하면서 부모보다 더 작은지 큰지를 확인해가며 노드의 위치를 옮긴다. 이때 루트 노드이거나 부모 노드가 더 큰 경우에는 스왑을 종료한다. 이 또한 재귀적으로 호출되는 경우도 있다. 단순히 리프노드가 아닌 최하단의 우측에 있는 노드에 노드를 삽입하는 이유는 Complete binary tree를 만족시키기 위해서이다.

- 힙 정렬 또한 NlogN만큼의 정렬 알고리즘이 된다. 하나의 ReHeapDown에 대해서는 logN의 연산속도를 가진다.

4) Make Heap

- 초기에 많은 데이터를 가지고 힙을 초기화해야하는 경우가 존재할 수 있다. (바이너리 서치 트리를 구성할 때 하나하나 데이터를 넣어야하는데 이처럼 하나하나 데이터를 삽입해가며 힙을 구현하는 것은 다소 비효율적이다.) 이때 두가지 방법을 활용해 문제를 해결할 수 있다. 첫번째로는 아이템을 하나하나 넣으면서 reHeapUp하는 방법이 있을 수 있다. 두번째 방법은 모든 데이터를 삽입한 상태에서 (depth-1, depth-2, depth-3 ...)에 대해 순차적으로 선을 그어 서브트리를 만들어서 각각의 서브트리의 루트에 대해 reHeapDown을 할 수 있다. 처음에는 리프노드 윗단에서 선을 그어 만들어지는 서브트리에 대해 reHeapDown을 하면 서브트리 내에서 가장 큰 원소가 루트 노드에 위치하기에 서브 트리의 힙 구조를 유지할 수 있게된다. 이후 선의 위치를 위로 올려 서브트리를 다시 만들고 reHeapDown을 하는 과정을 반복한다. reHeapDown을 사용하는 방식이 더 좋은 방식이 된다.

5) HeapBase 구현 과제

- const = 0과 같이 순수가상함수를 만들면 구현부분은 상속받는 곳에서 정의한다. 여러명이서 프로젝트를 진행할 때 클래스를 설계를 하면서 상호작용하는 부분에 대해서 정의를 사전에 하게된다. 따라서 순수가상함수를 사용해서 인터페이스를 제시하면 이를 통해 무엇을 구현해야하는지 알 수 있게된다는 장점이 있다. 즉, 디자인적인 측면에서 이를 정의하는 것은 중요하다.

6) HeapBase 상속받아서 진행될 때 문제가 발생하는 부분

- 부모 클래스에 존재하는 멤버 변수에 접근하기 어려울 수 있다.

- 키워드가 완성되면 어느 한 부분에 정의가 있고, 다른 부분에는 심볼이 있어서 실제 구현하는 부분은 한곳에만 있어도 연결해줘서 실제 진행할 수 있도록 한다. 템플릿은 정적 바인딩을 사용하기에 컴파일 타임에 바인딩을 진행하는데 동적바인딩과 함께 진행한다면 문제가 발생하는 경우가 존재한다. 포인터는 동적 바인딩의 예시이다. 만약 템플릿 클래스 내에서 동적할당을 하는 포인터형으로 변수를 정의하고, 이를 상속받는다면 문제가 발생할 수 있다. 따라서 using HeapBase<T>: m_pHeap이라고 내부에 적어주거나 this 포인터를 사용할 수 있다. 템플릿은 코드의 유효성 부분은 컴파일 타임에 확인하지만 코드를 수행할 때 처리하는 것은 런타임에 진행된다. this 포인터로 처리한다면 표현식의 유효성을 런타임에 판단하게 된다. 따라서 this 포인터를 사용하면 문제를 해결할 수 있다.

Priority Queue

1) Priority Queue란?

- 단순한 큐와는 다르게 우선순위를 저장하는 변수가 필요하다. 이를 항상 heap으로 구현하는 것은 아니지만 일반적으로 heap을 통해 이를 구현한다.

- 정렬된 데이터 구조는 정렬된 상태를 유지하기 위해 삽입, 삭제에서 들이는 시간이 매우 오래걸린다. 하지만 우선순위 큐는 단순히 우선순위에 맞춰 데이터를 꺼낼 수 있어야하는 것에 초점을 두고 있기에 모든 데이터를 정렬할 필요가 없다. 즉, 가장 우선순위가 높은 것만 뽑으면 된다. 이에 따라 굳이 모두 정렬하지 않고, 힙을 사용해서 우선순위 큐를 사용하는 경우가 많다.

- 힙을 사용할 경우 deque와 enque에서는 각각 ReHeapDown, ReHeapUp을 사용해야한다.

2) Priority Queue의 내부 자료구조

- 정렬되지 않은 리스트: 한번 deque를 할때마다 전체에 대해 서치를 해야한다.

- 어레이 정렬 리스트: 탐색은 빠르지만 데이터를 삽입할 때 비용이 비싸다.

- 레퍼런스 정렬 리스트: 데이터의 크기가 큰 경우에는 데이터가 저장되어있는 어레이에 대해 스왑하는 것이 아니라 포인터 배열을 만들어서 정렬할 때마다 포인터가 가리키고 있는 순서를 바꿔준다.

- BST: 평균적으로 O(logN)만큼의 데이터 삽입, 삭제 시간을 가진다. 하지만 입력되는 데이터가 치우쳐져있는 형태로 입력되면 비효율적이게된다.