[자료구조] Ch9 Priority Queue

Junyoung Park·2022년 8월 11일

자료구조

목록 보기

7/7

최대 힙, 최소 힙을 통해 각각 구현 가능 → 정렬 기준에 대한 한 가지 종류의 우선순위 큐 반환. end가 그 우선순위를 가장 만족하는 루트 노드를 가리킨다
우선순위 큐 메소드: (1). 우선순위 해당 원소 리턴 $O(1)$ (2). 원소 삽입 $O(logn)$ (3). 우선순위 해당 원소 삭제 $O(logn)$

meldable single-ended pq: 두 개 이상의 우선순위 큐를 병합해 하나의 우선순위 큐로 만들어주는 자료구조 - leftist trees, binomial heaps
특정 원소 삭제 및 우선순위 감소 가능한 우선순위 큐: fibonacci heaps, pairing heaps

최소 우선순위 원소를 리턴하기
최대 우선순위 원소를 리턴하기
임의의 우선순위를 가진 원소를 삽입하기
최소 우선순위 원소를 삭제하기
최대 우선순위 원소를 삭제하기

네트워크 버퍼에 DEPQ가 사용될 수 있다! 우선순위를 가진 패킷을 해당 큐에 받는다고 하자. 가장 먼저 보내야 하는(=우선순위 최대) 패킷은 2번 연산으로, 패킷을 버퍼에 삽입할 때에는 3번 연산으로, 버퍼가 가득 찰 때에는 4번 연산으로 핸들링해야 한다!

meldable PQ을 사용하는 효율적인 트리 구조
n: 병합될 두 우선순위 큐가 가지고 있는 모든 원소 개수
연산 속도: 삽입과 삭제 모두 logarithmic, 해당 우선순위 원소를 찾는 비용은 $O(1)$ 에 가능

힙을 사용할 때 병합은 $O(N)$ 이 걸린다!

확장된 이진 트리(extended binary tree) 채용 → internal nodes, external nodes 두 가지 종류
존재하지 않는 노드라 할지라도 전체 모든 노드(internal nodes)가 자식 노드 두 개를 가질 수 있도록 함

확장된 이진 트리의 노드 x: (1). leftChild(x) (2). rightChild(x) (3). shortest(x): 노드 x에서 출발, 다른 external node로 가는 가장 짧은 경로의 길이
shortest 계산: (1). external이라면 0 리턴 (2). internal이라면 두 자식 노드의 shortest 중 최솟값 + 1 리턴(재귀적 정의)
leftist trees는 (존재한다면) 왼쪽 자식 노드의 shortest가 우측 자식의 shortest보다 언제나 같거나 크다.
internal 노드 n개를 가지고 있는 leftist tree의 루트 노드 r이 있을 때 $n\geq2^{shortest(r)}-1$ 이고 루트 노드에서 가장 오른쪽에 치우쳐 있는 external 노드 경로는 $shortest(r)\leq log_2(n+1)$

shortest(r)의 정의에 따르면 첫 번째 $shortest(r)$ 레벨에서는 external 노드가 없다. 즉 적어도 $\sum^{shortest(r)}_{i=1}2^{i-1}=2^{shortest(r)}-1$ 개의 internal 노드를 가진다.

각 노드의 키 값이 자식 노드의 키 값보다 우선순위 정렬에 따르는 자료구조
최소/최대 leftist trees는 각각 일종의 최소/최대 트리
병합 연산을 통해 삽입 및 삭제 연산 가능
최소 leftist tree에 원소 x를 삽입할 때: (1). 하나의 원소 x만 가지고 있는 최소 leftist tree를 만들기 (20. 두 최소 leftist trees를 병합하기
최소 leftist tress에서 최솟값을 삭제할 때: 루트 노드의 우측 서브 트리와 좌측 서브 트리를 병합하고 기존 루트 노드는 리턴

병합할 두 이진 트리의 원소를 rightmost 경로를 따라 모으면서 이진 트리 만들기
해당 이진 트리를 leftist tree로 만들기 위해 필요한 만큼 좌측, 우측 서브 트리를 바꾸기
재귀적으로 leftists tree의 왼쪽부터 붙을 브런치를 교환하면서 만들어가기

leftist tree를 한 번 구성한 뒤에는 필요 조건인 shortest의 경로 길이가 좌측 서브 트리가 우측 서브 트리보다 같거나 커야 한다는 점을 만족할 수 있도록 계속해서 교환하자!

HBLT처럼 트리 내 external 노드까지의 경로 길이가 아니라 트리를 구성하는 노드의 개수를 고려하는 자료 구조
특정한 노드 x의 가중치인 $w(x)$ 는 루트 노드 x 및 서브트리의 internal 노드 개수다.
extenral 노드일 때에는 가중치 값은 0
internal 노드일 때에는 자식 노드의 가중치를 합한 데 + 1을 리턴

external 노드의 가중치 값이 0이기 때문에 리프 노드부터 계산, 루트 노드까지 가중치 값을 계산하는 게 보다 편리하다!
모든 internal 노드에서 좌측 자칙의 가중치 값이 우측 자식 가중치 값 이상이라면 WBLT로 간주할 수 있다.

최대, 최소 WBLT는 곧 WBLT인 최대, 최소 트리이다!
WBLT의 특정 노드 x는 해당 노드에서 가장 우측에 있는(rightmost)까지의 길이가 $rightmost(x)\leq log_2(w(x)+1)$ 을 만족한다.

Leftist trees에서 지원 가능한 모든 함수 가능
삽입, 삭제, 병합 등 개별 연산이 $O(logn)$ 에 가능한 leftist trees에 비해 특정 상황에서는 $O(n)$ 이 걸릴 수도 있음 → 비용이 큰 연산을 비용이 작은 연산에 amortize할 때 시간 복잡도를 $O(1)$ 또는 $O(logn)$ 에 할 수 있음.
(1). 최소 트리의 집합 - 최소 이진 힙 (2). 최대 트리의 집합 - 최대 이진 힙
이진 힙 노드: (1). degree: 자식의 개수 (2). child: 자식 노드에 대한 포인터 (3). link: sibling과 단일 연결 원형 리스트로 구성 (4). data
노드의 모든 자식: 단일 연결 원형 리스트로 구성 및 포인터
최소 트리의 루트: 단일 연결 원형 리스트로 링크
가장 키 값이 작은 최소 트리의 루트 노드에 대한 단일 포인터 min이 해당 이진 힙을 포인터로 가리키고 있음

이진 힙의 min이 가리키는 값을 리턴한 뒤 생기는 서로 다른 트리를 다시 이진 힙 상태(각 트리의 degree가 서로 다른 상태)로 만드는 과정까지 포함
현재 min이 가리키고 있는 노드를 리턴, 해당 노드가 루트 노드인 이진 힙의 서브 트리를 분리
같은 degree를 가지고 있는 최소 트리 쌍을 조인
이진 힙의 정의(이진 힙 내 서로 다른 트리 루트 노드의 degree가 모두 다른 상태)를 만족할 때까지 반복