제 9 장 우선순위 큐

Transcription

1 제 9 장 우선순위큐 Copyright 007 DBLAB, Seoul National University

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

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

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

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

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

7 좌향트리 () 높이편향좌향트리 (height biased leftest tree:hblt) - 일반적으로 HBLT 를좌향트리라고함 x 로부터외부노드까지의최단경로의길이 0 (x 가외부노드인경우 ) - shortest(x) +min {shortest(leftchild(x)),shortest(rightchild(x))} ( 그밖의경우 ) - LeftChild(x) : 내부노드 x의왼쪽자식 - RightChild(x) : 내부노드 x의오른쪽자식 Copyright 007 DBLAB, Seoul National University 7

8 좌향트리 () 정의 - 이진트리로서트리가공백이아닌경우모든내부노드 x 에대해다음식을만족 shortest(leftchild(x)) shortest(rightchild(x)) B A C D E F J H G I 보조정리 9. (a) 좌향트리아님 (b) 좌향트리 - n 개의내부노드를가진좌향트리의루트 : r - n shortest(r) - - shortest(r)= 루트로부터외부노드까지의가장오른쪽경로 shortest(r) log (n+) Copyright 007 DBLAB, Seoul National University

9 최소 ( 최대 ) 좌향트리 각노드의키값이그노드의자식들의키값보다크지 ( 작지 ) 않은좌향트리. 좌향트리이면서최소 ( 최대 ) 트리 최소좌향트리의예 (a) (b) Copyright 007 DBLAB, Seoul National University 9

10 최소좌향트리의합병 () 루트비교 < 3 - 가루트 의오른쪽서브트리와루트가 인이진트리합병 Copyright 007 DBLAB, Seoul National University 0

11 최소좌향트리의합병 () 루트비교 < 가루트 의오른쪽서브트리와루트가 0 인이진트리합병 Copyright 007 DBLAB, Seoul National University

12 최소좌향트리의합병 (3) 루트비교 <0, 의오른쪽서브트리없음 루트가 0 인이진트리와루트가 인이진트리합병 Copyright 007 DBLAB, Seoul National University

13 최소좌향트리의합병 () 루트가 인이진트리와루트가 인이진트리합병 루트가 인이진트리와루트가 인이진트리합병 Copyright 007 DBLAB, Seoul National University 3

14 최소좌향트리의합병 () shortest(leftchild()) shortest(rightchild()) 서브트리교환 서브트리교환 Copyright 007 DBLAB, Seoul National University

15 가중치편향좌향트리 () 가중치 w(x) - 루트가 x 인서브트리에있는내부노드의수 - 내부노드의가중치 = 자식들의가중치합계 + - 외부노드의가중치 = 가중치편향좌향트리 (weight-biased liftest tree:wblt) - w(leftchild(x)) w(rightchild(x)) 인이진트리 최대가중치편향좌향트리 - 가중치편향좌향트리이면서최대트리 Copyright 007 DBLAB, Seoul National University

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

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

18 이항히프 () 최소이항히프 (min-binomial heap) - 최소트리의집합 - B- 히프 최대이항히프 - 최대트리의집합 최소이항히프의예 상환시간 - 삽입, 합병 : O() - 최소 - 삭제 : O(log n) Copyright 007 DBLAB, Seoul National University

19 이항히프 () 구조 - 노드구조 degree : 자식의수 child : 자식중의하나 link : 형제사이의단순연결원형리스트를유지하는데사용 data - 최소트리들의루트는단순연결원형리스트로연결 - min은최소값을갖는트리를가리킴 min Copyright 007 DBLAB, Seoul National University 9

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

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

22 최소원소를삭제한후의 B- 히프 차수가 인두최소트리를조인 차수가 인두최소트리를조인 Copyright 007 DBLAB, Seoul National University

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

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

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

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

27 F- 히프에서의삭제 F- 히프에서임의의노드 b 삭제.min==b 이면최소 - 삭제. 그렇지않을경우,3, 수행.b 가속한이중연결리스트에서 b 삭제 3.b 의자식의이중연결리스트와 min 이가리키는이중연결리스트합병. 차수가같은트리조인은생략. 노드 b 제거 min 삭제후 실행비용 : O() Copyright 007 DBLAB, Seoul National University 7

28 키감소 노드 b 의키값감소.b 의키값감소. b 최소트리루트 and b 의키 < 부모의키 이면 - b 를이중연결리스트에서삭제 - 최소트리루트의이중연결리스트에삽입 3. b 의키 <min 의키 이면 - min 이 b 를가리키도록변경 min min 실행비용 : O() 를 감소 Copyright 007 DBLAB, Seoul National University

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

30 를 감소 * (a) Copyright 007 DBLAB, Seoul National University 30 0 (b)

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

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

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

34 최소페어링히프예 Copyright 007 DBLAB, Seoul National University 3

35 합병과삽입 () 비교링크 (compare-link) - 두최소페어링히프를하나의최소페어링히프로합병 - 두최소트리의루트를비교, 더큰루트를가진최소트리가다른트리의가장왼쪽서브트리가됨 - 합병예 삽입 - 원소 x 를가진페어링히프를만든후두페어링히프합병 Copyright 007 DBLAB, Seoul National University 3

36 합병과삽입 () Copyright 007 DBLAB, Seoul National University 3

37 키감소 노드 N 이루트 or N 의감소시킨키 부모노드의키 - 키감소후종료 변경된키 < 부모노드의키 - 트리에서루트가 N 인서브트리분리 - 두최소트리를합병 Copyright 007 DBLAB, Seoul National University 37

38 Copyright 007 DBLAB, Seoul National University 3 최소 - 삭제 () 루트노드 ( 최소원소 ) 삭제후남은최소트리들을합병 단계페어링히프 (two pass pairing heap) 에서의합병. 왼쪽에서오른쪽으로진행하면서트리쌍들을합병 루트삭제

39 최소 - 삭제 ().. 가장오른쪽트리에서시작하여한번에하나씩남아있는트리를이트리에합병 ( 오른쪽에서왼쪽으로 ) 단계 () Copyright 007 DBLAB, Seoul National University 39

40 Copyright 007 DBLAB, Seoul National University 0 최소 - 삭제 (3) 다단계패스페어링히프 (multi pass pairing heap) 의합병 - FIFO 큐에최소트리들삽입 - 큐앞에서 개뽑아합병후큐뒤에삽입 - 트리하나남을때까지반복

41 임의삭제 N 이루트일때 - 최소 - 삭제연산으로처리 N 이루트가아닐때. 트리에서루트가 N인서브트리분리. 노드 N 삭제후, 서브트리들을하나의최소트리로합병 3.,로부터나온최소트리들을하나로합병 Copyright 007 DBLAB, Seoul National University

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

43 대칭최소 - 최대히프 (SMMH) 루트는공백 루트를제외한각노드들이정확히하나의원소만갖는완전이진트리 elements(n) Ø 라면 - elements(n) : N 에있는원소를제외하고 N 을루트로하는서브트리에있는원소 - N 의왼쪽자식은 elements(n) 에있는최소원소 - N 의오른쪽자식은 elements(n) 에있는최대원소 Copyright 007 DBLAB, Seoul National University 3

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

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

46 SMMH 로의삽입 (). 완전이진트리의크기를 확장삽입될원소 x 를위한새노드 E 생성 0 삽입 E 로 x 를삽입한결과가 P 에위배되는지검증위배되는경우, E 의형제에있는원소는 E 로이동,E 는공백인형제노드를갖도록갱신 30 E Copyright 007 DBLAB, Seoul National University

47 SMMH 로의삽입 () 3. E 로부터트리위쪽으로 P 와 P3 을검증하면서버블업패스 (bubble-up pass) 수행 x 를 E 로삽입해도 P 와 P3 을위배하지않게되는곳에 E 가위치했을때 x 를 E 에삽입 과 E 교환 0 E E > : P 위배 Copyright 007 DBLAB, Seoul National University 7

48 SMMH 로의삽입 (3) 0 0 E 0 와 E 교환 E > : P 위배 E E 에 삽입 P,P,P3 모두만족 Copyright 007 DBLAB, Seoul National University

49 SMMH 에 0 을삽입하는예제 () E E <0 : P3 위배 P,P,P3 모두만족 E 에 0 삽입 Copyright 007 DBLAB, Seoul National University 9

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

51 최소 - 삭제예제 () 0 E x = 0 0> : P 위배 E > : P 위배 30 x = E에 x 삽입 E x = 0 Copyright 007 DBLAB, Seoul National University

52 최소 - 삭제예제 () 0 E 삭제 > : P 위배 x= E x=0 0 0 E 30 x=0 0> : P 위배 0>30 : P 위배 Copyright 007 DBLAB, Seoul National University

53 최소 - 삭제예제 (3) E 0 x=30 E 에 x 삽입 복잡도 : O(log n) Copyright 007 DBLAB, Seoul National University 3

54 구간히프 (interval heap) 마지막노드를제외한각노드가두개의원소 (a,b 이고 a b) 를포함하고있는완전이진트리 닫힌구간 [a,b] 를표현 각노드 P 의자식들의구간은 P 의구간에포함됨,30 3,7,, 3,,0,,0,,9,7, 7,9 Copyright 007 DBLAB, Seoul National University

55 구간히프의성질 노드구간의왼쪽끝점은최소히프를, 오른쪽끝점은최대히프를정의 (a) 최소히프 (b) 최대히프 루트의왼쪽끝점은구간히프에서최소원소, 오른쪽끝점은최대원소루트가하나의원소를가질때는최소이자최대원소 배열에사상시키는방식으로표현 n 개의원소를갖는구간히프의높이 : Ɵ(log n) Copyright 007 DBLAB, Seoul National University

56 구간히프로의삽입,30,0,, 3,7,,9 3,,7,,0 7,9 A, x 삽입 <x< : A 에삽입 x < : 최소히프에삽입 x > : 최대히프에삽입,30, 3,7, 3,,0, 0 삽입 <0< : A 에삽입,0,,9,7, 7,9 0 Copyright 007 DBLAB, Seoul National University

57 구간히프에 3 을삽입하는예제,30,30 3,7, 3,7,, 3,,0,, 3,,0,,0,,9,7, 7,9 A,0,,9,7, 7,9 3< 이므로최소히프삽입 3< 이므로 을아래로이동,30 3,7,,30 3,7 3,, 3,,0,, 3,,0,,0,,9,7, 7,9,0,,9,7, 7,9 3< 이므로 를아래로이동 3> 이므로 3 삽입 Copyright 007 DBLAB, Seoul National University 7

58 구간히프에 0 을삽입하는예제,30 3,7,,30 3,7,, 3,,0,, 3,,0,,0,,9,7, 7,9 A,0,,9,7, 7,9 0> 이므로최대히프삽입 0> 이므로 를아래로이동,30 3,7,,0 3,7,30, 3,,0,, 3,,0,,0,,9,7, 7,9,0,,9,7, 7,9 0> 이므로 를아래로이동 0>30 이므로 30 을아래로이동, 0 삽입 Copyright 007 DBLAB, Seoul National University

59 홀수개의원소를가진구간히프에삽입,0,0,, 3,7,30 3,,0,9,7, 7,9 A, x 삽입 <x< : A 에삽입 (x<a. : x 가왼쪽끝점 ) x< : 최소히프에삽입 x> : 최대히프에삽입,0 3,7,3 3 삽입 : 최대히프삽입, 3,,0,30,0,,9,7, 7,9, Copyright 007 DBLAB, Seoul National University 9

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

61 최소원소삭제예제 (),0 B 3,7,3,0 p= B 3,7,3, C 3,,0,30, C 3,,0,30,0,,9 D,7, 7,9,,0, D,9,7, 7,9 B의 3<, 3을루트로이동, 3,0 3,0 p= B,7,3 B 3,7,3, C 3,,0,30, p= C,,0,30,0,,9 D,7, 7,9,,0,,9 D,7, 7,9, 7, B 의오른쪽점과교환하지않음 C 의 3<, 3 을 B 로이동 >, p 와 교환 Copyright 007 DBLAB, Seoul National University

62 최소원소삭제예제 () 3,0 3,0 B 3,7,3 B 3,7,3,,0,,9 C, p=,0 D,7, 7,9,,30,0,,,9 C, p= D,7,,0 7,9,,30 D 의 <, 를 C 로이동 >7, p 와 7 교환 3,0 3,0 3,7,3 3,7,3,, p=7,0,30,,,0,30,0,,9,, 7,9,0,,9 7,, 7,9 p 삽입 Copyright 007 DBLAB, Seoul National University

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

64 구간히프연산의복잡도 GetMin() : O() GetMax() : O() Insert() : O(log n) DeleteMin() : O(log n) DeleteMax() : O(log n) 초기화 : Ɵ(n) Copyright 007 DBLAB, Seoul National University

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