우선순위 큐
우선순위 큐란, 우선순위의 개념을 Queue에 도입한 자료 구조를 의미합니다. 데이터들이 우선 순위를 가지고 있고, 들어온 순서에 상관 없이 우선 순위가 높은 데이터가 먼저 나가게 됩니다. 네트워크 트래픽 제어,운영 체제에서의 작업 스케줄링, 수치 해석적인 계산 등의 작업에 주로 사용됩니다.
우선순위 큐가 배열이나 연결리스트로 구현되지 않는 이유
우선순위가 중간인 데이터가 삽입되어야 하는 과정에서 삽입해야 하는 위치를 찾기위해 모든 인덱스를 탐색해야 하며, 뒤의 인덱스까지 모두 한 칸씩 뒤로 밀어야 합니다. 이 때 시간 복잡도는 자료가 n개 일 때 O(n)이 됩니다. 삭제의 경우 O(1)
힙 (heap)
힙(heap)이란 완전 이진 트리를 기초로 하는 자료구조로, 여러 개의 값들 중 최대값 혹은 최소값을 빠르게 찾아낼 수 있도록 만들어졌습니다. 힙은 다음과 같은 특징을 갖고 있습니다.
- 우선 순위 큐를 만들 때 사용하는 자료구조
- 힙의 부모 노드의 값은 항상 자식 노드의 값보다 크게 정렬되어 있다.
- 이진 탐색 트리와는 다르게 중복 값을 허용한다.
- 힙은 최대힙과 최소힙으로 나뉘어지는데, 최대힙은 자식의 노드 값이 부모의 노드 값보다 작거나 같은 힙(부모값 ≥ 자식값)을 의미하고, 최소힙은 자식의 노드 값이 부모의 노드 값보다 크거나 같은 힙(부모값 ≤ 자식값)을 의미한다.
힙(heap)의 구현
힙을 저장하는 표준적인 자료 구조는 배열입니다. 완전이진트리를 기본으로 하기 때문에 비어있는 공간이 없어 배열로 구현하기에 용이합니다.
Root 노드를 배열의 0번 index에 저장하고, 각 노드를 기점으로 왼쪽 자식 노드는 a[i*2 + 1], 오른쪽 자식 노드는 a[i*2 + 2]에 저장합니다. 또한 특정 index 노드의 부모 노드는 a[⌊(i-1) / 2⌋]로 찾을 수 있습니다.
힙(heap)의 삽입과 삭제
힙은 항상 최대힙 또는 최소힙의 규칙을 따르지만, 힙에서 삽입 또는 삭제가 발생할 경우 해당 규칙이 깨질 수도 있습니다. 이러한 경우에 원래 규칙을 만족할 수 있도록 노드들의 위치를 바꿔가며 힙을 재구조화(heapify)해야 합니다.
힙의 삽입과 삭제의 연산은 O(1)로 동작하지만, heapify의 과정을 거치게 될 경우 O(logN)의 시간 복잡도를 갖게 됩니다.
삽입 과정
아래 그림은 새로운 노드가 삽입되었을 경우를 나타냅니다. 새로운 노드는 가장 말단에 있는 노드의 자식 노드로 추가되고, 이후 부모 노드와 비교하며 재구조화 과정을 수행합니다. 삽입 과정은 아래에서 위로 재구조화 과정이 수행됩니다.
아래는 heap과 삽입 과정을 구현한 코드입니다.
삭제 과정
아래 그림은 루트 노드가 삭제되었을 경우를 나타냅니다. 루트 노드가 삭제되면 가장 말단 노드를 루트 노드 자리에 대체한 후 재구조화 과정을 수행합니다. 힙으로 구현된 우선순위 큐에서도 가장 우선순위가 큰 루트 노드를 주로 삭제합니다. 삭제 과정은 위에서 아래로 재구조화 과정이 수행됩니다.
아래는 삭제 과정을 구현한 코드입니다.
