제 9 장 우선순위 큐.

Presentation on theme: "제 9 장 우선순위 큐."— Presentation transcript:

1 제 9 장 우선순위 큐

2 한쪽 끝과 양쪽 끝 우선순위 큐 우선순위 큐(priority queue) 최소 우선순위 큐에서의 연산
각 원소가 연관된 우선순위를 갖고 있는 원소들의 모임 최소 우선순위 큐에서의 연산 SP1: 최소 우선순위를 가진 원소의 반환 SP2: 임의의 우선순위를 가진 원소의 삽입 SP3: 최소 우선순위를 가진 원소의 삭제 최대 우선순위 큐에서의 연산 SP1: 최대 우선순위를 가진 원소의 반환 SP3: 최대 우선순위를 가진 원소의 삭제 히프 구현 SP1 : O(1) SP2, SP3 : O(log n)

3 합병성 우선순위 큐 합병성(한쪽 끝)(meldable(single-ended)) 우선순위 큐 합병성 우선순위 큐의 확장
두 개의 우선순위 큐를 합병해서 SP1~SP3의 연산을 확장 하나의우선순위 큐를 가진 서버가 멈췄을 때 적용 가능 작동 되는 서버의 우선 순위 큐와 합병 좌향 트리(leftist tree), 이항 히프(binomial heap) 합병성 우선순위 큐의 확장 임의 원소를 삭제 임의 원소의 키/우선순위 감소(또는 증가) 피보나치 히프(Fibonacci heap), 페어링 히프(pairing heap)

4 양쪽 끝 우선순위 큐(DEPQ) 최소 우선순위 큐와 최대 우선순위 큐가 하나의 구조로 합해진 최소 최대 우선순위 큐 연산
DP1 : 최소 우선순위를 가진 원소의 반환 DP2 : 최대 우선순위를 가진 원소의 반환 DP3 : 임의의 우선순위를 가진 원소의 삽입 DP4 : 최소 우선순위를 가진 원소의 삭제 DP5 : 최대 우선순위를 가진 원소의 삭제 사용 예 네트워크 버퍼 외부 퀵 정렬

5 외부 퀵 정렬 내부 DEPQ가 찰 때까지 원소들을 메모리로 읽음 나머지 원소를 한번에 하나씩 처리
if 다음 원소 ≤ DEPQ의 가장 작은 원소 이 원소를 왼쪽 그룹으로 elseif 다음 원소 ≥ DEPQ의 가장 큰 원소 이 원소를 오른쪽 그룹으로 else 최대 또는 최소 원소 제거 최대 원소가 제거 되었을 경우, 최대 원소를 오른쪽 그룹으로 최소 원소가 제거 되었을 경우, 최소 원소를 왼쪽 그룹으로 새로운 원소를 DEPQ에 삽입 중간 그룹으로 DEPQ에 있는 원소를 정렬된 순서로 출력 왼쪽과 오른쪽 그룹에 대해 순환적으로 정렬

6 확장 이진 트리(extended binary tree)
모든 공백 이진 서브트리를 정사각형 노드로 대체 정사각형 노드 : 외부 노드(external node) 원래의 (원형) 노드 : 내부 노드(internal node) A B C D E F (a) G H I J (b)

7 좌향 트리 (1) 높이 편향 좌향 트리(height biased leftest tree:HBLT)
x로부터 외부 노드까지의 최단 경로의 길이 0 (x가 외부 노드인 경우) shortest(x) 1+min {shortest(LeftChild(x)),shortest(RightChild(x))} (그 밖의 경우) LeftChild(x) : 내부노드 x의 왼쪽 자식 RightChild(x) : 내부노드 x의 오른쪽 자식

8 좌향 트리 (2) 정의 이진 트리로서 트리가 공백이 아닌 경우 모든 내부 노드 x에 대해 다음 식을 만족 shortest(LeftChild(x)) ≥ shortest(RightChild(x)) 보조정리 9.1 n개의 내부노드를 가진 좌향트리의 루트 : r n ≥ 2shortest(r)-1 shortest(r)=루트로부터 외부 노드까지의 가장 오른쪽 경로 shortest(r) ≤ log2(n+1) A B C D E F (a) 좌향트리 아님 2 1 G H I J (b)좌향트리

9 최소(최대) 좌향 트리 각 노드의 키 값이 그 노드의 자식들의 키 값보다 크지(작지) 않은 좌향 트리.
좌향트리이면서 최소(최대) 트리 최소 좌향 트리의 예 2 7 50 11 13 80 1 5 9 8 12 20 10 18 15 (a) (b)

10 최소 좌향 트리의 합병 (1) 루트 비교 2<5 2가 루트 2의 오른쪽 서브트리와 루트가 5인 이진트리 합병 2 2 2
7 50 9 8 1 1 2 1 11 80 12 10 1 1 1 1 13 20 18 15 1 2 2 5 1 1 1 1 7 50 9 8 1 1 2 1 11 80 12 10 1 1 1 1 13 20 18 15

11 최소 좌향 트리의 합병 (2) 루트 비교 5<50 5가 루트 5의 오른쪽 서브 트리와 루트가 50인 이진트리 합병 1 1
7 80 1 9 8 2 1 11 12 10 1 1 1 1 13 20 18 15 1 1 1 2 5 50 1 1 1 1 8 7 9 1 80 1 2 10 11 12 1 1 1 1 15 13 20 18

12 최소 좌향 트리의 합병 (3) 루트 비교 8<50, 8의 오른쪽 서브트리 없음
루트가 50인 이진트리와 루트가 8인 이진트리 합병 1 1 1 1 2 5 50 8 1 1 1 1 7 9 80 10 1 2 1 11 12 15 1 1 1 13 20 18 1 1 2 2 5 8 1 1 1 1 7 9 10 50 1 2 1 1 11 12 15 80 1 1 1 13 20 18

13 최소 좌향 트리의 합병 (4) 루트가 5인 이진트리와 루트가 8인 이진트리 합병
루트가 2인 이진트리와 루트가 5인 이진트리 합병 1 2 2 5 1 1 2 7 9 8 1 2 1 1 11 12 10 50 1 1 1 1 1 13 20 18 15 80 2 2 1 2 7 5 2 1 2 11 9 8 1 2 1 1 13 12 10 50 1 1 1 1 20 18 15 80

14 최소 좌향 트리의 합병 (5) shortest(LeftChild())≥shortest(RightChild()) 2 2 2 2
1 2 1 2 7 5 7 5 2 1 2 서브트리 교환 2 2 1 11 9 8 11 8 9 1 2 1 1 1 1 1 2 13 12 10 50 13 10 50 12 1 1 1 1 1 1 1 1 20 18 15 80 15 80 20 18 2 2 2 2 1 2 2 1 7 5 서브트리 교환 5 7 2 2 1 2 1 2 11 8 9 8 9 11 1 1 1 2 1 1 2 1 13 10 50 12 10 50 12 13 1 1 1 1 1 1 1 1 15 80 20 18 15 80 20 18

15 가중치 편향 좌향 트리 (1) 가중치 w(x) 루트가 x인 서브트리에 있는 내부 노드의 수 내부노드의 가중치 = 자식들의 가중치 합계 +1 외부노드의 가중치 = 0 가중치 편향 좌향 트리(weight-biased liftest tree:WBLT) w(LeftChild(x)) ≥ w(RightChild(x))인 이진 트리 최대 가중치 편향 좌향 트리 가중치 편향 좌향 트리이면서 최대 트리 6 3 2 1 4

16 가중치 편향 좌향 트리 (2) 보조정리 9.2 가중치 편향 트리의 연산
rightmost(x) = x에서 외부 노드까지 가장 오른쪽 경로 길이 rightmost(x) ≤ log2(w(x)+1) 증명 w(x)=1이면 rightmost(x)=1이고, log2(w(x)+1)=log2(2)=1 w(x)<n이면 항상 rightmost(x)≤log2(w(x)+1)라고 가정 w(x)=n이면 w(RightChild(x))≤(n-1)/2이고 rightmost(x)= 1+rightmost(RightChild(x)) ≤ 1+ log2((n-1)/2+1) = 1+ log2(n+1) = log2(n+1) 가중치 편향 트리의 연산 삽입, 최대-삭제, 초기화 연산 : 최대 HBLT 연산과 유사 합병 연산 : 한 번의 하향식 과정으로 수행

17 비용 상환 어떤 연산의 실제 비용을 다른 연산에 부과 상환 비용 : 그 연산에 부과된 총 비용
어느 한 연산에 부과된 비용 감소 / 다른 연산의 비용 증가 상환 비용 : 그 연산에 부과된 총 비용 연산 순서의 복잡도에 있어 보다 엄격한 한계값 얻을 수 있음 개별 연산 시간 보다 전체 시간에 관심이 있는 응용에 적합 e.g. 정렬

18 이항 히프 (1) 최소 이항 히프(min-binomial heap) 최대 이항 히프 최소 이항 히프의 예 상환 시간
최소 트리의 집합 B-히프 최대 이항 히프 최대 트리의 집합 최소 이항 히프의 예 상환 시간 삽입, 합병 : O(1) 최소-삭제 : O(log n) 8 10 3 5 6 4 1 12 16 15 20 7 30 9

19 이항 히프 (2) 구조 노드 구조 최소 트리들의 루트는 단순 연결 원형 리스트로 연결 min은 최소 값을 갖는 트리를 가리킴
degree : 자식의 수 child : 자식 중의 하나 link : 형제 사이의 단순 연결 원형 리스트를 유지하는데 사용 data 최소 트리들의 루트는 단순 연결 원형 리스트로 연결 min은 최소 값을 갖는 트리를 가리킴 8 10 3 5 6 4 1 12 16 15 20 7 30 9 min

20 이항 히프에서의 연산 이항 히프에서의 삽입 두 이항 히프의 합병 새로운 노드에 x를 넣음
min이 가리키는 원형 리스트에 이 노드를 넣음 만약 min이 0이거나 현재 최소 값보다 x의 키가 작으면 min이 새로운 노드를 가리키도록 변경 O(1) 두 이항 히프의 합병 최 상위 원형 리스트를 하나의 원형 리스트로 합병. 두 트리의 min 포인터 중 작은 값을 가리키게 변경

21 이항 히프에서 최소 원소 삭제 공백 B-히프의 처리 공백이 아닌 B-히프에서의 삭제 최소 트리 조인
if(!min) throw QueueEmpty(); 공백이 아닌 B-히프에서의 삭제 x=min→data; y=min→child; 원형리스트에서 min을 삭제 min은 결과 리스트에 남아있는 임의의 노드를 가리킴 그런 노드가 없으면 min=0;  최소 트리 조인 리스트 min과 y의 최소 트리들에 대해, 이 최소 트리가 모두 서로 다른 차수를 가질 때까지 차수가 같은 최소 트리들을 둘씩 서로 조인 최소 트리 루트 리스트의 구성 최소 트리의 루트들을 전부 연결하여 원형 리스트로 구성 min이 가장 작은 키를 가진 루트를 가리키도록 한다 x를 반환;

22 8 10 3 5 6 4 12 16 15 20 7 30 9 최소 원소를 삭제한 후의 B-히프 8 10 3 5 6 4 12 16 15 20 7 30 9 차수가 1인 두 최소 트리를 조인 8 10 3 5 6 4 12 16 15 20 7 30 9 차수가 2인 두 최소 트리를 조인

23 최소-삭제 연산의 복잡도 단계 1: O(1) 단계 2: O(1) 단계 3: O(maxDegree + s)
s : min과 y에 있는 최소 트리의 수 tree[] : 0부터 maxDegree까지 인덱스 된 배열 단계 4: O(maxDegree) tree[0], ... , tree[maxDegree]를 조사하여 발견된 최소 트리를 서로 연결 가장 작은 키 값을 가진 최소 트리 결정  for (d = p->degree; tree[d]; d++)   {       JoinMinTrees(p,tree[d]);       tree[d] = 0;   }   tree[d] = p;

24 이항 히프 분석 (1) 이항 트리 차수가 k인 이항트리 Bk는 k=0이면 하나의 노드만 가지고 있고, k>0이면 서브트리 B0,B1, ..., Bk-1을 갖는 차수 k인 루트로 구성된 트리 Bk는 정확히 2k개의 노드를 가짐 보조정리 9.3 a는 처음에 공백인 B-히프에서 시작하여 삽입, 합병, 최소-삭제 연산을 통해 얻어진 n개의 원소를 가진 B-히프. a의 각 최소 트리의 차수 ≤ log2n maxDegree ≤ 최소-삭제의 실제 비용 : O(log n +s)

25 이항 히프 분석 (2) 정리 9.1 i회 삽입, c회 합병, dm회 최소-삭제
빈 B-히프에 대해 총 n개의 삽입, 합병, 최소-삭제 연산 삽입, 합병 연산의 상환된 시간 복잡도 : O(1) 최소-삭제 연산의 상환된 시간 복잡도 : O(log n) i회 삽입, c회 합병, dm회 최소-삭제 O(i+c+dm log i)

26 피보나치 히프 최소 피보나치 히프(F-히프) / 최대 피보나치 히프 B-히프는 F-히프의 특수한 경우 연산 구조
GetMin, Insert, DeleteMin, Meld : B-히프와 같음 Delete(임의 삭제) : O(log n) 명기된 노드에서 원소 삭제 DecreaseKey(키 감소) : O(1) 명기된 노드에서 주어진 양수만큼 키/우선순위 감소 구조 B-히프의 각 노드에 parent와 childCut 데이타 멤버 추가 parent : 그 노드의 부모 childCut : 추후 설명 단순 연결 원형 리스트 → 이중 연결 원형 리스트 link → leftLink, rightLink

27 F-히프에서의 삭제 F-히프에서 임의의 노드 b 삭제 실행 비용 : O(1)
min==b 이면 최소-삭제. 그렇지 않을 경우 2,3,4 수행 b가 속한 이중 연결 리스트에서 b 삭제 b의 자식의 이중 연결 리스트와 min이 가리키는 이중 연결 리스트 합병. 차수가 같은 트리 조인은 생략 노드 b 제거 실행 비용 : O(1) 8 10 3 5 6 4 1 12 16 15 20 7 30 9 삭제 후 min

28 키 감소 노드 b의 키 값 감소 실행비용 : O(1) b의 키 값 감소
‘b≠최소 트리 루트’ and ‘b의 키<부모의 키’이면 b를 이중 연결 리스트에서 삭제 최소 트리 루트의 이중 연결 리스트에 삽입 ‘b의 키<min의 키’이면 min이 b를 가리키도록 변경 실행비용 : O(1) min 8 10 3 5 6 4 1 12 16 15 20 7 30 9 15를 4 감소 11

29 연쇄 분리(cascading cut) bool 데이타 멤버 childCut
x가 가장 최근에 현재 부모의 자식으로 된 이후 x의 자식 중 하나가 삭제될 경우 true 두 최소 트리가 조인될 때 더 큰 키를 가진 루트의 childCut은 false로 설정 삭제, 키-감소 연산에서 루트가 아닌 노드 q를 삭제할 때마다 연쇄 분리 단계 호출 q의 부모 p에서부터 childCut=false인 가장 가까운 조상에 이르는 경로 검사 그런 조상이 없으면 p부터 p가 속한 최소 트리의 루트까지 검사 이 경로 상에 childCut이 true이면서 루트가 아닌 모든 노드들을 삭제하고 F-히프의 최소 트리 루트 노드의 이중 연결 리스트에 삽입 이 경로 상에서 childCut이 false인 것은 true로 변경

30 2 4 5 10 12 10 6 60 16 15 18 30 11 20 8 7 8 6 10 20 7 14를 4 감소 30 12 11 2 * 4 5 14 18 60 16 15 (b) (a)

31 분석 보조정리 9.4 공백인 F-히프에 일련의 삽입, 합병, 최소-삭제, 삭제, 키-감소 연산을 수행하여 n개의 원소를 가진 F-히프a가 되었다고 할 때 b는 a의 한 최소 트리에 있는 임의의 노드라고 하면 b의 차수≤ logφm (φ = , m=b의 서브트리의 원소 수) maxDegree ≤ 최소-삭제의 실제 비용 : O(logn+s) 정리 9.2 처음에 공백인 F-히프에 대해 n번의 삽입, 합병, 최소-삭제, 삭제, 키-감소 연산을 수행 할 때 삽입, 합병, 키-감소 연산의 상환 시간 복잡도 : O(1) 최소-삭제, 삭제 연산의 상환 시간 복잡도 : O(log n)

32 최단-경로 문제에 응용 하나의 출발점과 모든 목표점에 대한 최단-경로 문제 S : 최단 경로가 찾아진 정점들의 집합
dist(i) S에 있는 정점만을 통해 출발점에서 i로 가는 최단 경로의 길이 최소-삭제 연산 dist(i)가 최소가 되는 i(i∈ )를 S에 첨가 n-2번 수행 키-감소 연산 에 남아 있는 정점의 dist 값이 작아질 때 그래프의 간선 수(e) 만큼 수행 n-1번 삽입+n-2번 최소-삭제+e번 키-감소 = O(nlogn+e)

33 페어링 히프(pairing heap) GetMin,Insert,DeleteMin,Meld,Delete,DecreaseKey연산
최대 페어링 히프 / 최소 페어링 히프 우선순위 큐를 표현하는데 사용 피보나치 히프와 페어링 히프 연산의 복잡도 비교 연산 피보나치 히프 페어링 히프 실제 상환 GetMin Insert DeleteMin Meld Delete DecreaseKey O(1) O(n) O(log n)

34 최소 페어링 히프 예 6 8 2 3 9 5 1 4 7

35 합병과 삽입(1) 비교 링크(compare-link) 삽입 두 최소 페어링 히프를 하나의 최소 페어링 히프로 합병
두 최소 트리의 루트를 비교, 더 큰 루트를 가진 최소 트리가 다른 트리의 가장 왼쪽 서브트리가 됨 합병 예 삽입 원소 x를 가진 페어링 히프를 만든 후 두 페어링 히프 합병 2 3 9 6 5 8 1 4 7

36 합병과 삽입(2) 2 3 9 6 5 8 1 4 7 3 6 5 2 3 9 6 5 8 1 4 7

37 키 감소 노드 N이 루트 or N의 감소시킨 키 ≥ 부모 노드의 키 변경된 키 < 부모 노드의 키 키 감소 후 종료
두 최소 트리를 합병 1 5 6 4→0 3 7

38 최소-삭제 (1) 루트 노드(최소 원소) 삭제 후 남은 최소 트리들을 합병
2단계 페어링 히프(two pass pairing heap)에서의 합병 왼쪽에서 오른쪽으로 진행하면서 트리 쌍들을 합병 4 9 5 3 6 8 1 7 4 9 5 3 6 8 1 7 루트 삭제 4 9 3 6 5 1 7 8

39 최소-삭제 (2) 가장 오른쪽 트리에서 시작하여 한번에 하나씩 남아 있는 트리를 이 트리에 합병(오른쪽에서 왼쪽으로) 3 6
5 1 8 7 4 9 3 6 5 1 8 7 4 9 단계2 (2)

40 최소-삭제 (3) 다단계 패스 페어링 히프(multi pass pairing heap)의 합병 FIFO 큐에 최소 트리들 삽입
큐 앞에서 2개 뽑아 합병 후 큐 뒤에 삽입 트리 하나 남을 때까지 반복 4 9 5 3 6 8 1 7 4 9 3 6 5 1 7 8 3 6 5 4 9 1 8 7 3 6 5 4 9 1 8 7

41 임의 삭제 N이 루트일 때 N이 루트가 아닐 때 최소-삭제 연산으로 처리 트리에서 루트가 N인 서브트리 분리
1,2로부터 나온 최소 트리들을 하나로 합병

42 구현 고려 사항과 복잡도 구현 고려사항 복잡도 다양한 수의 자식 필드를 가진 노드로 구현 이진 트리로 구현
자식 필드 수를 동적으로 증가 → 비용 증가 이진 트리로 구현 형제 노드들을 이중 연결 리스트로 구현 가장 왼쪽에 있는 노드는 부모 노드를 가리킴 이중 연결 리스트 사용시 O(1) 시간에 임의 원소 삭제 가능 복잡도 GetMin,Insert,,Meld,DecreaseKey : O(1) DeleteMin,Delete : O(n) 노드 삭제후 합병되어야 하는 서브트리의 수가 O(n)

43 대칭 최소-최대 히프(SMMH) 루트는 공백 루트를 제외한 각 노드들이 정확히 하나의 원소만 갖는 완전 이진 트리
elements(N)≠Ø 라면 elements(N) : N에 있는 원소를 제외하고 N을 루트로 하는 서브트리에 있는 원소 N의 왼쪽 자식은 elements(N)에 있는 최소 원소 N의 오른쪽 자식은 elements(N)에 있는 최대 원소 8 20 12 60 16 10 6 30 14 4 80 40

44 SMMH의 성질 P1. 각 노드의 원소는 오른쪽 형제에 있는 원소보다 작거나 같다.
P2. 조부모를 가진 모든 노드 N에 대하여 조부모의 왼쪽 자식에 있는 원소는 N에 있는 원소보다 작거나 같다. P3. 조부모를 가진 모든 노드 N에 대하여 조부모의 오른쪽 자식에 있는 원소는 N에 있는 원소보다 크거나 같다.

45 SMMH 표현 완전 이진 트리를 1차원 배열(h)로 표현 루트를 표현하는 위치 1은 비어 있음
last : h의 제일 오른쪽 위치 SMMH의 크기 = last -1 arrayLength : h에 있는 위치들의 현재 수 최소 반환, 최대 반환 연산 : O(1) n=1 : 최소와 최대 원소 동일. 루트의 왼쪽 자식 n>1 : 최소 원소는 루트의 왼쪽, 최대 원소는 루트의 오른쪽

46 SMMH로의 삽입 (1) 완전 이진 트리의 크기를 1 확장 삽입될 원소 x를 위한 새 노드 E 생성
E로 x를 삽입한 결과가 P1에 위배되는지 검증 위배되는 경우, E의 형제에 있는 원소는 E로 이동,E는 공백인 형제 노드를 갖도록 갱신 8 20 12 60 16 10 6 30 14 4 80 40 E 2 삽입

47 SMMH로의 삽입 (2) E로부터 트리 위쪽으로 P2와 P3을 검증하면서 버블업 패스(bubble-up pass) 수행 x를 E로 삽입해도 P2와 P3을 위배하지 않게 되는 곳에 E가 위치했을 때 x를 E에 삽입 8 20 12 60 16 10 E 30 14 4 80 40 6 8 20 12 60 16 10 6 30 14 4 80 40 E 6과E교환 6>2 : P2 위배

48 SMMH로의 삽입 (3) 8 20 12 60 16 10 4 30 14 E 80 40 6 8 20 12 60 16 10 E 30 14 4 80 40 6 4와E교환 4>2 : P2 위배 8 20 12 60 16 10 4 30 14 E 80 40 6 8 20 12 60 16 10 4 30 14 2 80 40 6 E에 2 삽입 P1,P2,P3 모두 만족

49 SMMH에 50을 삽입하는 예제 (1) 8 20 12 60 16 10 4 30 14 2 80 40 6 E 8 20 12 60 16 10 4 30 14 2 80 E 6 40 40<50 : P3 위배 P1,P2,P3 모두 만족 8 20 12 60 16 10 4 30 14 2 80 50 6 40 E에 50 삽입

50 SMMH에서의 삭제 최소 원소 h[2] 삭제 last를 1 감소한 후, h[last]를 SMMH에 재 삽입
P1과 P2 성질들 확인하면서 x를 삽입할 적당한 노드에 도달할 때까지 트리 아래쪽으로 경로를 따라감 최소-삭제 연산인 경우 P3에 위배될 수 없음.

51 최소-삭제 예제 (1) 8 20 12 60 16 10 4 30 14 2 80 50 6 40 8 20 12 60 16 10 4 30 14 E 80 50 6 x = 40 40>4 : P2 위배 8 20 12 60 16 10 E 30 14 4 80 50 6 x = 40 40>6 : P2 위배 8 20 12 60 16 10 6 30 14 4 80 50 E x = 40 E에 x 삽입

52 최소-삭제 예제 (2) 8 20 12 60 16 10 6 30 14 4 80 50 40 4 삭제 8 20 12 60 16 10 6 30 14 E 80 50 x=40 40>6 : P2 위배 8 20 12 60 16 10 E 30 14 6 80 50 x=40 40>14 : P2 위배 8 20 12 60 16 10 14 30 E 6 80 50 x=40 40>30 : P1 위배

53 최소-삭제 예제 (3) 8 20 12 60 16 10 14 40 E 6 80 50 x=30 E에 x 삽입 복잡도 : O(log n)

54 구간 히프(interval heap) 마지막 노드를 제외한 각 노드가 두 개의 원소(a,b이고 a≤b)를 포함하고 있는 완전 이진 트리 닫힌 구간 [a,b]를 표현 각 노드 P의 자식들의 구간은 P의 구간에 포함 됨 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6,15 2,30

55 구간 히프의 성질 노드 구간의 왼쪽 끝 점은 최소 히프를, 오른쪽 끝 점은 최대 히프를 정의
루트의 왼쪽 끝 점은 구간 히프에서 최소 원소, 오른쪽 끝 점은 최대 원소 루트가 하나의 원소를 가질 때는 최소이자 최대 원소 배열에 사상시키는 방식으로 표현 n개의 원소를 갖는 구간 히프의 높이 : Ɵ(log n) 2 30 3 4 17 15 4 3 5 6 12 11 10 15 4 5 5 4 8 7 10 11 9 7 8 9 (a) 최소 히프 (b) 최대 히프

56 구간 히프로의 삽입 10 삽입 x 삽입 6<x<15 : A에 삽입 x < 6 : 최소 히프에 삽입
4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6,15 2,30 A x 삽입 6<x<15 : A에 삽입 x < 6 : 최소 히프에 삽입 x > 15 : 최대 히프에 삽입 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6,15 2,30 10 10 삽입 6<10<15 : A에 삽입

57 구간 히프에 3을 삽입하는 예제 3<6 이므로 최소 히프 삽입 3<6 이므로 6을 아래로 이동
4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6,15 2,30 A 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 ,15 2,30 6 3<6 이므로 최소 히프 삽입 3<6 이므로 6을 아래로 이동 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 ,15 4 ,15 2,30 6 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 3,15 4,15 2,30 6 3<4 이므로 4를 아래로 이동 3>2 이므로 3 삽입

58 구간 히프에 40을 삽입하는 예제 40>15 이므로 15를 아래로 이동 40>15 이므로 최대 히프 삽입
4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6, 2,30 15 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,15 6,15 2,30 A 40>15 이므로 최대 히프 삽입 40>15 이므로 15를 아래로 이동 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4, 4 ,15 2,30 6 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,30 6,15 2,40 15 40>15 이므로 15를 아래로 이동 40>30 이므로 30을 아래로 이동, 40 삽입

59 홀수개의 원소를 가진 구간 히프에 삽입 x 삽입 6<x<15 : A에 삽입 (x<A.15 : x가 왼쪽 끝점)
4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,30 6,15 2,40 15 x 삽입 6<x<15 : A에 삽입 (x<A.15 : x가 왼쪽 끝점) x<6 : 최소 히프에 삽입 x>15 : 최대 히프에 삽입 A 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,32 6,30 2,40 15,15 32 삽입 : 최대 히프 삽입

60 최소 원소 삭제 구간 히프가 비어 있으면 DeleteMin 실패
구간 히프가 오직 하나의 원소를 가질 때, 이 원소를 반환하고 공백 구간 히프가 됨 둘 이상의 원소가 있을 경우 루트의 왼쪽 끝 점 반환,제거 루트가 마지막 노드가 아닐 경우 마지막 노드에서 왼쪽 점 p 제거 후 최소 히프에 p 재삽입 (마지막 노드가 공백이 되면 노드 제거)

61 최소 원소 삭제 예제 (1) p=15 p=15 p=15 B의 3<15, 3을 루트로 이동
4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,32 6,30 ,40 ,15 B C D p=15 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 3,17 4,32 6,30 2,40 15,15 B C D B의 3<15, 3을 루트로 이동 4,12 5,11 4,10 3,11 4,7 5,9 5,10 7,9 8,8 ,17 4,32 6,30 3,40 ,15 B C D 4,12 5,11 4,10 ,11 4,7 5,9 5,10 7,9 8,8 3 ,17 4,32 6,30 3,40 ,15 B C D p=15 p=15 15≤17, B의 오른쪽 점과 교환 하지 않음 C의 3<15, 3을 B로 이동 15>11, p와 11 교환

62 최소 원소 삭제 예제 (2) p=11 p=11 D의 4<11, 4를 C로 이동 11>7, p와 7 교환 p=7
4,12 5,11 4,10 ,15 4,7 5,9 5,10 7,9 8,8 3 ,17 4,32 6,30 3,40 B C D 4,12 5,11 4,10 4,15 ,7 5,9 5,10 7,9 8,8 3 ,17 4,32 6,30 3,40 ,15 B C D p=11 p=11 D의 4<11, 4를 C로 이동 11>7, p와 7 교환 4,12 5,11 4,10 4,15 ,11 5,9 5,10 7,9 8,8 3,17 4,32 6,30 3,40 15 4,12 5,11 4,10 4,15 7,11 5,9 5,10 7,9 8,8 3,17 4,32 6,30 3,40 15 p=7 p 삽입

63 구간 히프의 초기화 각 서브 트리가 구간 히프인지 확인하면서 히프 제일 밑에서부터 루트까지 검사 각 서브트리에 대해
루트에 있는 원소들을 순서화 DeleteMin에 사용된 재삽입 방법을 이용, 서브트리의 루트의 왼쪽 끝 점을 재삽입 DeleteMax에 사용된 방법을 이용, 서브트리의 루트의 오른쪽 끝 점을 재삽입

64 구간 히프 연산의 복잡도 GetMin() : O(1) GetMax() : O(1) Insert() : O(log n)
DeleteMin() : O(log n) DeleteMax() : O(log n) 초기화 : Ɵ(n)

65 보완적 범위 탐색 문제 일차원 점들의 동적인 모임이 주어졌을 때 구간 [a,b]의 밖에 있는 점 탐색
보완적 범위 질의 : Ɵ(k) (단 k는 답이 되는 점들의 수) 구간 히프가 비어 있다면 반환 루트 구간이 [a,b]에 포함된다면, 반환 - 모든 점들이 범위 안에 있으므로, 답이 없음 범위 [a,b]에 없는 루트 구간의 끝점들이 답이 됨 루트의 왼쪽 서브트리를 순환적으로 탐색 루트의 오른쪽 서브 트리를 순환적으로 탐색 반환 방문된 구간 히프 노드들의 총 수 : O(3k+1)