우선순위 큐
Last updated
Last updated
큐는 FIFO 이지만 우선순위 큐(Priority Queue;PQ) 는 들어간 순서에 상관 없이 우선순위 가 높은 데이터가 먼저 나온다. =>우선순위 어떻게 설정하는가? =>기본적으로 정수, 문자, 문자열 같은 경우 언어에서 지원하는 기본 정렬 기준들이 있다. =>예를 들어 정수나 문자의 경우 낮은 값이 높은 값보다 우선한다! 최소힙과 최대힙 두가지가 있다. ① 최소힙 : 부모 노드 값(key) <= 자식 노드 값(key) ② 최대힙 : 부모 노드 값(key) >= 자식 노드 값(key) 최소힙 <=> 최대힙 : 비교 연산자만 바꿔주면 됨. 많은 언어들은 오름차순을 기본으로 하기 때문에 '최소힙'을 구현해보도록 한다!
우선순위 큐는 각 요소들이 각각의 우선 순위를 갖고 있고, 요소들의 대기열에서 '우선 순위가 높은 요소'가 '우선 순위가 낮은 요소'보다 먼저 제공되는 자료구조이다.
우선순위 큐(PQ) != 힙 PQ는 힙과 유사한 구조를 갖고 있으나, 개념 자체는 엄연히 다르다. 힙 : 최솟값 또는 최댓값을 빠르게 찾아내기 위한 완전이진트리 형태로 만들어진 자료구조 즉, 힙의 중점이 되는 것은 '최솟값 또는 최댓값 빠르게 찾기' PQ : 우선순위가 높은 순서대로 요소를 제공
힙에서 '최대 혹은 최솟값 빠르게 찾기' => PQ "우선순위가 높은 요소를 빠르게 찾기" 어떤 리스트에 값을 넣거나 뺄 때 우선순위가 높은 것부터 빼내려고 하면 그 때마다 정렬을 해야한다. 따라서 효율적으로 값을 가져오기 위해 힙을 항성 정렬된 상태로 유지한다. "부모 노드는 항상 자식 노드보다 우선순위가 높다" 는 기준으로 말이다. 이렇게 하면 O(1)의 복잡도로 우선순위가 놓은 것을 빠르게 찾아낼 수 있고, 삽입/삭제 연산 시에도 부모 노드가 자식 노드보다 우선 순위만 높으면 되기 때문에 트리의 깊이만큼만 비교하면 되기 때문에 O(logN)의 시간 복잡드롤 가져 매우 빠르게 수행할 수 있다. (나의 해석)총 노드 갯수가 2^3 -1 개라고 한다면 깊이는 3이다. 3 = logN = log2^3 따라서 깊이만큼 비교한다면 이 깊이는 logN이기 때문에 시간 복잡도는 O(logN)이 된다.
일반적인 형태의 큐는 선형적인 형태를 가지고 있지만 우선순위 큐는 트리 구조로 보는 것이 합리적이다.
그렇다면 트리 구조를 어떻게 구현할 수 있나? 가장 표준적으로 구현되는 방식은 '배열'이다. 물룐 연결리스트로도 구현이 가능하긴 하지만, 문제는 특정 노드의 '검색','이동' 과정이 조금 더 번거롭기 때문이다. 배열의 경우, 특정 인덱스에 바로 접근할 수 있기 때문에 좀 더 효율적이기도 하다.
배열로 구현할 경우 특장점
왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2
오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 X 2 + 1
부모 노드 인덱스 = 자식 노드 인덱스 / 2
구현 방법
배열 기반
연결리스트 기반
힙 이용
배열이나 연결리스트로 구현할 경우, 간단하게 구현할 수 있지만 데이터를 삽입, 삭제하는 과정에서 데이터를 한칸 씩 당기거나 밀어야 하는 연산을 계속해야하고, 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
연결리스트의 경우, 삽입의 위치를 찾기 위해 첫번째 노드부터 시작해 마지막 노드에 저장된 데이터와 우선순위 비교를 진행해야 할 수도 있다. => 성능 저하.
따라서 최대힙으로 구현하는 것이 가장 적절하다.
최대힙이란?(Max Heap)
부모 노드가 자식 노드보다 값이 큰 완전 이진트 => 모든 부모 노드가 자식보다 값이 커야한다.
최대힙의 root node는 항상 최댓값을 갖는다.
전체 트리가 최대 힙 구조를 유지하도록 자료구조를 만들어야 한다.
PQ 삽입
삽입할 원소는 완전 이진트리를 유지하는 형태로 순차적으로 삽입된다.
삽입 이후에는 상향식으로 루트 노드까지 거슬러 올라가는 방식으로 최대힙을 구성한다.
즉, 부모노드와 비교를 해서 부모노드가 삽입한 노드의 값보다 작다면 교체한다. (logN의 시간복잡도)
PQ 삭제
삭제할 때는 루트 노드를 삭제하고, 가장 마지막 원소를 루트 노드의 위치로 옮긴다.
