이 챕터에서, 우리는 다른 정렬 알고리즘을 소개한다: heapsort. merge sort처럼, 하지만 insertion sort와는 다르게, heapsort의 런타임은 O(nlg(n))이다. insertion sort 처럼 하지만 merge sort와는 다르게, heapsort는 제자리에서 정렬한다: 오직 배열 원소들의 일정한 개수만이 언제든지 입력 배열의 밖에 저장된다. 따라서, heapsort는 우리가 이미 이야기 한 두 정렬 알고리즘의 좋은 특성들을 결합한다.
Heapsort는 또한 다른 알고리즘 디자인 테크닉을 도입한다: 자료구조를 사용하여, 이 경우에 우리는 정보를 관리하기 위해 heap이라고 부르는 것을. heap 자료구조는 heapsort에 유용할 뿐만 아니라, 그것은 효율적인 우선순위 큐를 만든다. heap 자료구조는 나중의 챕터의 알고리즘들에서 다시 나타날 것이다.
"heap이라는 용어는 원래 heapsort의 맥락에서 만들어졌다, 하지만 그것은 이후로, "garbage-collected storage"를 언급하게 되었다, 프로그래밍 언어인 Java와 Lisp가 제공하는 것처럼. 우리의 heap 자료구조는 garbage-collected storage가 아니고, 우리가 이 책에서 heaps을 언급할 때 마다, 우리는 garbage collection의 측면이라기 보다는 자료구조를 의미할 것이다.
6.1 Heaps
(binary) heap 자료구조는 그림 6.1에서 보여지듯이, 우리가 거의 완전 이진 트리 (see Section B.5.3)로 볼 수 있는 것이다. 트리의 각 노드는 그 배열의 한 요소와 일치한다. 그 트리는 완전히 가장 낮은 것을 제외하고 모든 수준에서 채워진다. 그리고 그 가장 낮은 것은 왼쪽에서부터 하나씩 채워진다. heap을 나타내는 배열 A는 두 개의 특성을 가진 오브젝트이다: A.length는 (보통) 배열에 있는 원소들의 개수를 주고, A.heap-size는 heap에 얼마나 많은 요소들이 배열 A에 저장되는지를 나타낸다. 즉, 비록 A[1..A.length]가 숫자를 포함할지라도, 오직 A[1..A.heap-size]에 있는 원소들은 heap의 유효한 원소들이다. 여기에서 0 <= A.heap-size <= A.length 이다. 트리의 root는 A[1]이고, 한 노드의 인덱스 i가 주어진다면, 우리는 쉽게 그것의 부모, 왼쪽 child, 오른쪽 child의 인덱스들을 연산할 수 있다:
Parent(i)
1 return [i/2]
Left(i)
1 return 2i
Right(i)
1 return 2i + 1
대부분의 컴퓨터에서, Left 절차는 간단히 i의 이진 표현을 왼쪽으로 한 비트 shift하여 2i를 연산할 수 있다. 유사하게, Right 절차는 빠르게 i의 이진 표현을 왼쪽으로 한 비트 shift하고 낮은 자리에 1을 더하여 2i+1의 연산할 수 있다. Parent 절차는 i를 오른쪽으로 shift하여 연산할 수 있다. heapsort의 좋은 구현은 종종 이러한 절차들을 marcos 또는 in-line 절차로서 구현한다.
binary heap에 두 가지 종류들이 있다: max-heaps and min-heaps. 두 종류에서, 노드들에 있는 값들은 heap property를 만족한다. 그것들의 세부사항들은 그 힙의 종류에 의존한다. max-heap에서 max-heap property는 root를 제외한 모든 노드 i에 대해,
A[Parent(i)] >= A[i],
즉, 한 노드의 값은 많아봐야 그것의 부모 값이라는 것이다. 따라서, max-heap의 가장 큰 원소는 root에 저장되어있고, 한 노드를 root로하는 subtree는 그 노드 자체에 포함된 값보다 더 크지 않은 값들을 포함한다. min-heap은 반대로 구성된다; min-heap property는 root를 제외한 모든 노드 i에 대해,
A[Parent(i)] <= A[i]
min-heap에서 가장 작은 원소는 root에 있다.
heapsort 알고리즘에 대해, 우리는 max-heaps를 사용한다. Min-heaps는 흔히 우선순위 큐를 구현한다. 우리는 Section 6.5에서 이것을 이야기 한다. 우리는 우리가 어떤 특정한 프로그램에 대해 max-heap 또는 min-heap 필요한 지에 대해 명시하는데 정화하게 할 것이고, properties가 max-heaps 또는 min-heaps 둘 중 하나에 적용 될 때, 우리는 그냥 "heap"이라는 단어를 사용한다.
heap를 tree로서 본다면, 우리는 한 heap에서 한 노드의 높이를 그 노드에서 leaf로 가는 가장 길고, 간단한, 아래로가는 길에서의 edge의 개수로 정의한다. n개의 원소가 있는 한 heap은 완전 이진 트리를 기반으로 하기 때문에, 그것의 높이는 Θ(lg(n)이다. 우리는 heaps에서의 기본 연산들을 많아봐야 그 트리의 높이에 비례하여 작동한다고 볼 것이고, 따라서 O(lg(n)) 시간이 걸린다. 이 챕터의 나머지는 기본적인 절차들을 나타내고, 그것들이 정렬 알고리즘에서 그리고 우선순위 큐 자료구조에서 어떻게 사용되는지를 보여준다.
- MAX-HEAPIFY 절차는 O(lg(n)) 시간에서 작동하는데, max-heap property를 유지하는 열쇠이다.
- BUILD-MAX-HEAP 절차는, 선형 시간에서 작동하는데, 순서가 없는 input 배열으로부터 max-heap을 만들어낸다.
- HeapSort 절차는, O(nlg(n)) 시간에서 작동하는데, 한 배열을 제자리에서 정렬한다.
- MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEA-MAXIMUM 절차들은 O(lg(n))에서 작동하고, heap 자료구조가 우선순위 큐를 구현하도록 해준다.
6.2 Maintaining the heap property
max-heap property를 유지하기 위해서, 우리는 MAX-HEAPIFY 절차를 호출한다. 그것의 입력은 배열 A와 그 배열로 들어가는 한 인덱스 i이다. 그것이 호출될 때, MAX-HEAPIFY는 LEFT(i)와 RIGHT(i)를 root로 하는 이진 트리들이 max-heaps라고 가정하지만, A[i]는 그것의 childeren보다 작다고 가정한다. 따라서 max-heap property를 위반하고 있다. MAX-HEAPIFY는 A[i]에 있는 값이 max-heap에서 "float down"(흘러내려가게)한다. index i를 root로 하는 subtree가 max-heap property를 만족하게 하기 위해서이다.
MAX-HEAPIFY(A,i) 1 l = LEFT(i) 2 r = RIGHT(i) 3 if l <= A.heap-size and A[l] > A[i] 4 largest = l 5 else largest = i 6 if r <= A.heap-size and A[r] > A[largest] 7 largest = r 8 if largest != i 9 exchange A[i] with A[largest] 10 MAX-HEAPIFY(A, largest)
그림 6.2는 MAX-HEAPIFY의 행동을 보여준다. 각 단계에서, A[i], A[LEFT(i)], A[RIGHT(i)]원소들 중에서 가장 큰 것이 결정 되고, 그리고 그것의 index는 largest에 저장된다. 만약 A[i]가 가장 큰 것이라면, 그러면 노드 i를 root로 하는 subtree는 이미 max-heap이고 절차는 끝난다. 그렇지 않다면, 그 두 childerne 중의 하나는 가장 큰 원소를 갖고있는 것이고, A[i]는 A[largest]와 바꿔진다. 이것은 node i와 그것의 자식들이 max-heap property를 만족하게 한다. 그러나 largest로 인덱싱되는 그 노드는 이제 A[i]의 원래 값을 갖고, 따라서 largest를 root로 하는 subtree는 max-heap property를 위반할지도 모른다. 결과적으로 우리는 MAX-HEAPIFY를 그 subtree에서 재귀적으로 호출한다.
주어진 노드 i를 root로 하는 사이즈가 n인 subtree에서 MAX-HEAPIFY의 작동 시간은 원소들 A[i], A[LEFT(i)], A[RIGHT(i)] 중에서 관계를 고치는데 Θ(1), 더해서 NODE I의 자식들 중 하나를 root로 하는 subtree에서 MAX-HEAPIFY를 드는 시간이다. (재귀 호출이 발생한다고 가정하여). 자식들의 subtree의 각 사이즈는 많아봐야 2n/3이고 - 가장 나쁜 케이스는 그 트리의 bottom level이 정확히 절반정도 차있을 때 발생한다 - 그러므로 우리는 재귀적으로 MAX-HEAPIFY의 running-time을 묘사할 수 있다.
T(n) <= T(2n/3) + Θ(1)
이 재귀에 대한 솔루션은 마스터 정리 (정리 4.1)의 case2에 의하여, T(n) = O(lgn)이다. 대안적으로 우리는 높이가 h인 한 노드에서 MAX-HEAPIFY의 작동시간을 O(h)로 특징지을 수 있다.
6.3 Building a heap
우리는 한 배열 A[1..n] (n = A.length)을 max-heap으로 바꾸는 bottom-up 방식으로 MAX-HEAPIFY 프로시저를 사용할 수 있다. 연습문제 6.1-7에 의해, A[(n/2] +1)..n]인 subarray에서 원소들은 그 tree의 모든 leaves이다. 그래서 각각은 시작하는 1개의 element heap 이다. BUILD-MAX-HEAP 프로시저는 그 트리의 나머지 노드들로부터 시작하고, 각각에 대해 MAX-HEAPIFY를 작동시킨다.
그림 6.3은 BUILD-MAX-HEAP의 행동의 예쩨를 보여준다.
왜 BUILD-MAX-HEAP이 정확하게 작동하는지를 보여주기 위해서, 우리는 다음의 loop invariant를 사용한다:
lines 2-3의 for loop의 매 iteration의 시작에서, 각 노드의 i + 1, i + 2, ..., n은 한 max-heap의 root이다. (그러니까 그것을 root로하는 subtree가 max-heap property를 만족한다. 왜냐하면 n/2 + 1부터 leaf이기 때문에)
우리는 이 invariant가 첫 번째 loop iteration이전에 사실이라는 것을 보여줄 필요가 있고, loop의 매 반복이 그 invariant를 유지하고, 그 invariant는 그 loop가 끝날 때 옳다는 것을 보여줄 유용한 특성을 제공한다는 것을 보여줄 필요가 있다.
Initialization : loop의 첫 번째 반복 이전에 i = [n/2]이다. [n/2] + 1, [n/2] + 2,... ,n의 각 노드는 leaf이고 따라서 자명한 max-heap의 root이다.
Maintenance : 각 반복이 loop invariant를 유지하는지 보기 위해서, node i의 자식들이 i보다 높게 숫자를 부여받는지 관찰해라. loop invarinat에 의해, 그러므로 그것들 둘 다 max-heaps의 root들이다. 이것은 정확히 노드 i를 한 max-heap root로 만드는 MAX-HEAPIFY(A,i) 호출을 위해 요구되는 조건이다. 게다가, MAX-HEAPIFY 호출은 node i + 1, i + 2, ... , n의 노드들이 모드 max-heap의 root가 되는 특성을 보존한다. for loop update에서 i를 감소시키는 것은 다음 반복에 대한 loop invariant를 다시 설립한다.
Termination : 종료시에 i = 0이고, loop invariant에 의해 각 노드 1,2, ..., n은 max-heap의 root이고, 특히 node 1이 그렇다.
우리는 BUILD-MAX-HEAP의 작동시간에서 간단한 upper bound를 계산할 수 있다. MAX-HEAPIFY의 각 호출은 O(lg(n))의 시간을 쓰고, BUILD-MAX-HEAP은 O(n)의 호출을 한다. 따라서 작동시간은 O(nlg(n))이다. 이 upper bound은 정확할지라도, asymptotically tight하지 않다.
우리는 MAX-HEAPIFY가 한 노드에 대해 작동하는 시간이 그 트리에서의 노드의 높이와 함께 다르다는 것을 관찰하여 더욱 tight한 bound를 이끌어 낼 수 있고, 대부분의 노드들이ㅡ 높이는 작다. 우리의 tighter 분석은 n개의 원소를 가진 heap은 lgn의 높이를 갖고, 많아봐야 어떤 높이 h에서 [n/2^h+1]개의 노드들을 갖는다는 특성에 의존한다.
높이가 h인 한 노드에서 호출될 때, MAX-HEAPIFY에게 요구되는 시간은 O(h)이고, 그래서 우리는 BUILD-MAX-HEAP의 총 cost를 위로부터 제한하여 표현할 수 있다.
우리는 공식에서(A.8) x = 1/2로 치환하여 마지막 합을 구할 수 있다. 이것은 다음의 값을 만든다.
따라서, 우리는 BUILD-MAX-HEAP의 작동시간을 제한할 수 있다.
그러므로, 우리는 선형 시간에 정렬되지 않은 배열로부터 max-heap을 구성할 수 있다.
우리는 BUILD-MIN-HEAP 프로시저에 의해 min-heap을 구성할 수 있고, 그것은 BUILD-MAX-HEAP과 같지만, line 3에서 MAX-HEAPIFY에 대한 호출은 MIN-HEAPIFY에 대한 호출로 바꿔져야 한다. BUILD-MIN-HEAP은 정렬되지 않은 선형 배열로부터 선형 시간 안에 min-heap을 만들어 낸다.
6.4 The heapsort algorithm
heapsort 알고리즘은 입력 배열 A[1..n] (n = A.length)에서 max-heap을 구성하는 BUILD-MAX-HEAP을 사용하여 시작한다. 그 배열의 가장 큰 요소가 root인 A[1]에 저장되어 있기 때문에, 우리는 A[n]과 교환하여 그것을 그것의 정확하 마지막 위치에 넣을 수 있다. 만약 우리가 이제 그 힙으로부터 node n을 버린다면, - 그리고 우리는 간단히 A.heap-size를 줄여서 그러게 할 수 있다. - 우리는 그 root의 자식들은 max-heaps로 남지만, 그 새로운 root element max-heap property를 위반할지도 모른다. 그러나 max-heap property 복구하기 위해 우리가 해야할 필요가 있는 모든 것은 MAX-HEAPIFY(A,1)를 호출하는 것이고, 이것은 A[1..n-1]에서의 max-heap을 만들어낸다. heapsort algorithm은 그리고나서, size가 n-1인 max-heap에 대해 size가 2인 한 heap까지 이 프로세스를 반복한다.
그림 6.4는 line 1이 초기 max-heap을 구성한 후의 HEAPSORT의 연산의 예제를 보여준다. 그 그림은 lines 2-5의 for loop의 첫 번째 반복전의 max-heap을 보여주고, 매 반복마다 이후의 것을 보여준다.
HEAPSORT 절차는 O(nlg(n))의 시간이 걸린다. 왜냐하면 BUILD-MAX-HEAP이 O(n)이 걸리고, n-1개의 MAX-HEAPIFY에 대한 각 호출은 O(lg(n))이 걸리기 때문이다.
6.5 Priority queues
Heapsort는 훌륭한 알고리즘 이지만, Chapter 7에서 나타나는 quicksort의 좋은 구현은 실제로 보통 그것을 이긴다. 그럼에도 불구하고, heap 자료구조는 그 자체로 사용할 데가 많다. 이 섹션에서, 우리는 heap의 가장 인기있는 적용중의 하나를 보여준다: 효율적인 우선순위 큐로서. heaps과 함께, 우선순위 큐들은 두 가지 형태로 온다: max-priority queues와 min-priority queues. 우리는 여기에서 어떻게 max-priority queues를 구현할지에 집중할 것이고, 그 max-우선순위 큐는 차례대로 max-heaps을 기반으로 한다; 연습문제 6.5-3은 너에게 min-priority queues를 쓰라고 요구한다.
우선순위 큐는 key라고 불려지는 연관된 값을 가진 각각의 원소들의 한 집합 S를 유지하기 위한 자료구조이다. max-priority queue는 다음의 연산을 지원한다:
INSERT(S, x)는 element x를 집합 S에 넣는다, 이것은 연산 S = S U {x}와 같다.
MAXIMUM(S)는 가장 값이 큰 key를 가진 S의 원소를 반환한다.
EXTRACT-MAX(S)는 가장 값이 큰 key를 가진 S의 원소를 제거하고 반환한다.
INCREASE-KEY(S,x, k)는 원소 x의 key의 값을 새로운 값 k로 증가시킨다. 이것은 적어도 x의 현재 key 값만큼 크다고 가정되어진다.
그것들의 다른 적용 중에서, 우리는 shader computer에서 일들을 스케쥴링하는데 max-priority queue들을 사용할 수 있다. max-priority queue는 수행될 일들과 그것들의 상대적인 우선순위를 추적한다. 한 일이 끝내지거나 interrupted될 때, 그 스케쥴러는 그러한 것중에 EXTRACT-MAX를 호출하여 멈춰 있는 것들 중에서 가장 우선순위가 높은 일들을 선택한다. 그 스케쥴러는 언제든지 INSERT를 호출하여 큐에 새로운 일을 추가할 수 있다.
대안적으로 min-priority queue는 연산 INSERT, MINIMUM, EXTRACT-MIN, DECREASE-KEY를 지원한다. min-priority queue는 event-driven simulator에 사용되어질 수 있다. 큐에 있는 아이템들은 재현될 이벤트들이고, 각각은 그것의 key역할을 하는 발생할 연관된 시간 을 가지고 있다. 그 이벤트들은 발생 시간 순서대로 재현되어져야만 한다, 왜냐하면 한 사건의 재현은 다른 이벤트들이 미래에 재현되기를 만들 수 있기 때문이다. 재현 프로그램은 simulate할 다음 이벤트를 고르기 위해 각 단계에서 EXTRACT-MIN을 호출한다. 새로운 이벤트들이 만들어질 때, 그 simulator는 INSERT를 호출하여 min-priority queue 그것들을 넣는다.
우리는 Chapter 23과 24에서 DECREASE-KEY 연산을 강조하면서 min-priority queue들을 위한 다른 사용을 볼 것이다.
놀랍지 않게, 우리는 priority queue를 구현하기 위해 heap을 사용할 수 있다. 주어진 프로그램에서 job scheduling 또는 event-driven simulation과 같은 우선순위 큐의 원소들은 프로그램에서의 오브젝트들과 일치한다. 우리는 종종 어떤 프로그램 오브젝트가 주어진 우선순위 큐 요소에 일치하는지를 결정할 필요가 있다. 역으로도. 우리가 우선순위 큐를 구현하기 위해 힙을 사용할 때, 그러므로 우리는 종종 각 heap element에서 일치하는 프로그램 object에 대한 handle을 저장할 필요가 있다. (pointer 또는 integer 같은) 핸들의 정확한 구성은 프로그램에 의존한다. 유사하게, 우리는 각 프로그램의 오브젝트에서 상응하는 heap element에 대한 handle을 저장할 필요가 있다. 여기에서 handle은 일반적으로 array index이다. heap elements들은 heap operation동안 array내에서 위치를 바꾸기 때문에, heap element를 재위치시킬 때, 할 실제 구현은 또한 상응하는 프로그램 오브젝트에서 array index를 업데이트 시켜야 한다. application object들에 접근하는 세부사항은 크게 프로그램과 그것의 구현에 의존하기 때문에, 우리는 실제로 이러한 handles이 정확히 유지되어야 할 필요가 없다는 것을 주목하기 보다는 그것들을 여기에서 추구하지 않을 것이다.
이제 우리는 max-priority queue의 연산들을 어떻게 구현할지 이야기 한다. HEAP-MAXIMUM 절차는 Θ(1) 시간에 MAXIMUM 연산을 구현한다.
HEAP-EXTRACT-MAX 절차는 EXTRACT-MAX 연산을 구현한다. 그것은 HEAPSORT 절차의 for loo문(lines 3-5)와 유사하다.
HEAP-EXTRACT-MAX의 작동 시간은 O(lg(n))이다. 그것은 MAX-HEAPIFY를 위해 O(lg(n))의 시간 위에서 고정된 양의 작업을 하기 때문이다.
HEAP-INCREASE-KEY 절차는 INCREASE-KEY 연산을 구현한다. 배열에 들어가는 인덱스 i는 우리가 증가시키길 원하는 키의 우선순위 큐의 요소이다. 그 절차는 처음에 A[i]의 원소의 key를 그것의 새로운 값을 업데이트 시킨다. A[i]의 key를 증가시키는 것은 max-heap property를 위반하기 때문에, 그 절차는 그런 후에, Section 2.1의 INSERTION-SORT의 삽입 loop(lines 5-7)의 회상하는 방식으로, 새롭게 증가된 key를 위한 적절한 장소를 찾기 위해 이 노드부터 root까지 간단한 경로를 지나간다. HEAP-INCREASE-KEY가 이 경로를 지나갈 때, 그것은 반족으로 한 원소와 그것의 부모를 비교하고, 그것들의 키들을 교한하고, 그 원소의 키가 더 크다면 계속하고, 더 작다면 그만둔다. max-heap property가 이제야 유효하기 때문이다. (See Exercise 6.5-5 for a precise loop invariant.)
그림 6.5는 HEAP-INCREASE-KEY 연산의 한 예를 보여준다. n개의 요소를 가진 heap에서 HEAP-INCREASE-KEY 작동 시간은 O(lg(n))이다. line 3에서 업데이트 된 노드로부터 추적된 root로 가는 경로가 O(lg(n))이기 떄문이다.
MAX-HEAP-INSERT 절차는 INSERT 연산을 구현한다. 그것은 input으로서 max-heap A에 넣어질 새로운 원소의 key를 필요로 한다. 그 절차는 처음에 key가 -∞인 새로운 leaf를 트리에 더하여 max-heap을 확장한다. 그러고나서 이 새로운 노드의 KEY를 그것의 올바른 값으로 설정하고 max-heap property를 유지하기 위해 HEAP-ICREASE-KEY를 호출한다.
n개의 원소를 가진 heap에서 MAX-HEAP-INSERT의 작동시간은 O(lg(n))이다.
요약해서, 한 heap은 O(lg(n))시간에 사이즈가 n인 집합에서 어떤 priority-queue의 연산을 지원할 수 있다.
주어진 노드 i를 root로 하는 사이즈가 n인 subtree에서 MAX-HEAPIFY의 작동 시간은 원소들 A[i], A[LEFT(i)], A[RIGHT(i)] 중에서 관계를 고치는데 Θ(1), 더해서 NODE I의 자식들 중 하나를 root로 하는 subtree에서 MAX-HEAPIFY를 드는 시간이다. (재귀 호출이 발생한다고 가정하여). 자식들의 subtree의 각 사이즈는 많아봐야 2n/3이고 - 가장 나쁜 케이스는 그 트리의 bottom level이 정확히 절반정도 차있을 때 발생한다 - 그러므로 우리는 재귀적으로 MAX-HEAPIFY의 running-time을 묘사할 수 있다.
T(n) <= T(2n/3) + Θ(1)
이 재귀에 대한 솔루션은 마스터 정리 (정리 4.1)의 case2에 의하여, T(n) = O(lgn)이다. 대안적으로 우리는 높이가 h인 한 노드에서 MAX-HEAPIFY의 작동시간을 O(h)로 특징지을 수 있다.
6.3 Building a heap
우리는 한 배열 A[1..n] (n = A.length)을 max-heap으로 바꾸는 bottom-up 방식으로 MAX-HEAPIFY 프로시저를 사용할 수 있다. 연습문제 6.1-7에 의해, A[(n/2] +1)..n]인 subarray에서 원소들은 그 tree의 모든 leaves이다. 그래서 각각은 시작하는 1개의 element heap 이다. BUILD-MAX-HEAP 프로시저는 그 트리의 나머지 노드들로부터 시작하고, 각각에 대해 MAX-HEAPIFY를 작동시킨다.
BUILD-MAX-HEAP(A) 1 A.heap-size = A.length 2 for i = [A.length/2] downto 1 3 MAX-HEAPIFY(A,i)
그림 6.3은 BUILD-MAX-HEAP의 행동의 예쩨를 보여준다.
왜 BUILD-MAX-HEAP이 정확하게 작동하는지를 보여주기 위해서, 우리는 다음의 loop invariant를 사용한다:
lines 2-3의 for loop의 매 iteration의 시작에서, 각 노드의 i + 1, i + 2, ..., n은 한 max-heap의 root이다. (그러니까 그것을 root로하는 subtree가 max-heap property를 만족한다. 왜냐하면 n/2 + 1부터 leaf이기 때문에)
우리는 이 invariant가 첫 번째 loop iteration이전에 사실이라는 것을 보여줄 필요가 있고, loop의 매 반복이 그 invariant를 유지하고, 그 invariant는 그 loop가 끝날 때 옳다는 것을 보여줄 유용한 특성을 제공한다는 것을 보여줄 필요가 있다.
Initialization : loop의 첫 번째 반복 이전에 i = [n/2]이다. [n/2] + 1, [n/2] + 2,... ,n의 각 노드는 leaf이고 따라서 자명한 max-heap의 root이다.
Maintenance : 각 반복이 loop invariant를 유지하는지 보기 위해서, node i의 자식들이 i보다 높게 숫자를 부여받는지 관찰해라. loop invarinat에 의해, 그러므로 그것들 둘 다 max-heaps의 root들이다. 이것은 정확히 노드 i를 한 max-heap root로 만드는 MAX-HEAPIFY(A,i) 호출을 위해 요구되는 조건이다. 게다가, MAX-HEAPIFY 호출은 node i + 1, i + 2, ... , n의 노드들이 모드 max-heap의 root가 되는 특성을 보존한다. for loop update에서 i를 감소시키는 것은 다음 반복에 대한 loop invariant를 다시 설립한다.
Termination : 종료시에 i = 0이고, loop invariant에 의해 각 노드 1,2, ..., n은 max-heap의 root이고, 특히 node 1이 그렇다.
우리는 BUILD-MAX-HEAP의 작동시간에서 간단한 upper bound를 계산할 수 있다. MAX-HEAPIFY의 각 호출은 O(lg(n))의 시간을 쓰고, BUILD-MAX-HEAP은 O(n)의 호출을 한다. 따라서 작동시간은 O(nlg(n))이다. 이 upper bound은 정확할지라도, asymptotically tight하지 않다.
우리는 MAX-HEAPIFY가 한 노드에 대해 작동하는 시간이 그 트리에서의 노드의 높이와 함께 다르다는 것을 관찰하여 더욱 tight한 bound를 이끌어 낼 수 있고, 대부분의 노드들이ㅡ 높이는 작다. 우리의 tighter 분석은 n개의 원소를 가진 heap은 lgn의 높이를 갖고, 많아봐야 어떤 높이 h에서 [n/2^h+1]개의 노드들을 갖는다는 특성에 의존한다.
높이가 h인 한 노드에서 호출될 때, MAX-HEAPIFY에게 요구되는 시간은 O(h)이고, 그래서 우리는 BUILD-MAX-HEAP의 총 cost를 위로부터 제한하여 표현할 수 있다.
우리는 공식에서(A.8) x = 1/2로 치환하여 마지막 합을 구할 수 있다. 이것은 다음의 값을 만든다.
따라서, 우리는 BUILD-MAX-HEAP의 작동시간을 제한할 수 있다.
그러므로, 우리는 선형 시간에 정렬되지 않은 배열로부터 max-heap을 구성할 수 있다.
우리는 BUILD-MIN-HEAP 프로시저에 의해 min-heap을 구성할 수 있고, 그것은 BUILD-MAX-HEAP과 같지만, line 3에서 MAX-HEAPIFY에 대한 호출은 MIN-HEAPIFY에 대한 호출로 바꿔져야 한다. BUILD-MIN-HEAP은 정렬되지 않은 선형 배열로부터 선형 시간 안에 min-heap을 만들어 낸다.
6.4 The heapsort algorithm
heapsort 알고리즘은 입력 배열 A[1..n] (n = A.length)에서 max-heap을 구성하는 BUILD-MAX-HEAP을 사용하여 시작한다. 그 배열의 가장 큰 요소가 root인 A[1]에 저장되어 있기 때문에, 우리는 A[n]과 교환하여 그것을 그것의 정확하 마지막 위치에 넣을 수 있다. 만약 우리가 이제 그 힙으로부터 node n을 버린다면, - 그리고 우리는 간단히 A.heap-size를 줄여서 그러게 할 수 있다. - 우리는 그 root의 자식들은 max-heaps로 남지만, 그 새로운 root element max-heap property를 위반할지도 모른다. 그러나 max-heap property 복구하기 위해 우리가 해야할 필요가 있는 모든 것은 MAX-HEAPIFY(A,1)를 호출하는 것이고, 이것은 A[1..n-1]에서의 max-heap을 만들어낸다. heapsort algorithm은 그리고나서, size가 n-1인 max-heap에 대해 size가 2인 한 heap까지 이 프로세스를 반복한다.
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.length downto 2
3 exchange A[1] with A[i]
4 A.heap-size = A.heap-size - 1
5 MAX-HEAPIFY(A, 1)
그림 6.4는 line 1이 초기 max-heap을 구성한 후의 HEAPSORT의 연산의 예제를 보여준다. 그 그림은 lines 2-5의 for loop의 첫 번째 반복전의 max-heap을 보여주고, 매 반복마다 이후의 것을 보여준다.
HEAPSORT 절차는 O(nlg(n))의 시간이 걸린다. 왜냐하면 BUILD-MAX-HEAP이 O(n)이 걸리고, n-1개의 MAX-HEAPIFY에 대한 각 호출은 O(lg(n))이 걸리기 때문이다.
6.5 Priority queues
Heapsort는 훌륭한 알고리즘 이지만, Chapter 7에서 나타나는 quicksort의 좋은 구현은 실제로 보통 그것을 이긴다. 그럼에도 불구하고, heap 자료구조는 그 자체로 사용할 데가 많다. 이 섹션에서, 우리는 heap의 가장 인기있는 적용중의 하나를 보여준다: 효율적인 우선순위 큐로서. heaps과 함께, 우선순위 큐들은 두 가지 형태로 온다: max-priority queues와 min-priority queues. 우리는 여기에서 어떻게 max-priority queues를 구현할지에 집중할 것이고, 그 max-우선순위 큐는 차례대로 max-heaps을 기반으로 한다; 연습문제 6.5-3은 너에게 min-priority queues를 쓰라고 요구한다.
우선순위 큐는 key라고 불려지는 연관된 값을 가진 각각의 원소들의 한 집합 S를 유지하기 위한 자료구조이다. max-priority queue는 다음의 연산을 지원한다:
INSERT(S, x)는 element x를 집합 S에 넣는다, 이것은 연산 S = S U {x}와 같다.
MAXIMUM(S)는 가장 값이 큰 key를 가진 S의 원소를 반환한다.
EXTRACT-MAX(S)는 가장 값이 큰 key를 가진 S의 원소를 제거하고 반환한다.
INCREASE-KEY(S,x, k)는 원소 x의 key의 값을 새로운 값 k로 증가시킨다. 이것은 적어도 x의 현재 key 값만큼 크다고 가정되어진다.
그것들의 다른 적용 중에서, 우리는 shader computer에서 일들을 스케쥴링하는데 max-priority queue들을 사용할 수 있다. max-priority queue는 수행될 일들과 그것들의 상대적인 우선순위를 추적한다. 한 일이 끝내지거나 interrupted될 때, 그 스케쥴러는 그러한 것중에 EXTRACT-MAX를 호출하여 멈춰 있는 것들 중에서 가장 우선순위가 높은 일들을 선택한다. 그 스케쥴러는 언제든지 INSERT를 호출하여 큐에 새로운 일을 추가할 수 있다.
대안적으로 min-priority queue는 연산 INSERT, MINIMUM, EXTRACT-MIN, DECREASE-KEY를 지원한다. min-priority queue는 event-driven simulator에 사용되어질 수 있다. 큐에 있는 아이템들은 재현될 이벤트들이고, 각각은 그것의 key역할을 하는 발생할 연관된 시간 을 가지고 있다. 그 이벤트들은 발생 시간 순서대로 재현되어져야만 한다, 왜냐하면 한 사건의 재현은 다른 이벤트들이 미래에 재현되기를 만들 수 있기 때문이다. 재현 프로그램은 simulate할 다음 이벤트를 고르기 위해 각 단계에서 EXTRACT-MIN을 호출한다. 새로운 이벤트들이 만들어질 때, 그 simulator는 INSERT를 호출하여 min-priority queue 그것들을 넣는다.
우리는 Chapter 23과 24에서 DECREASE-KEY 연산을 강조하면서 min-priority queue들을 위한 다른 사용을 볼 것이다.
놀랍지 않게, 우리는 priority queue를 구현하기 위해 heap을 사용할 수 있다. 주어진 프로그램에서 job scheduling 또는 event-driven simulation과 같은 우선순위 큐의 원소들은 프로그램에서의 오브젝트들과 일치한다. 우리는 종종 어떤 프로그램 오브젝트가 주어진 우선순위 큐 요소에 일치하는지를 결정할 필요가 있다. 역으로도. 우리가 우선순위 큐를 구현하기 위해 힙을 사용할 때, 그러므로 우리는 종종 각 heap element에서 일치하는 프로그램 object에 대한 handle을 저장할 필요가 있다. (pointer 또는 integer 같은) 핸들의 정확한 구성은 프로그램에 의존한다. 유사하게, 우리는 각 프로그램의 오브젝트에서 상응하는 heap element에 대한 handle을 저장할 필요가 있다. 여기에서 handle은 일반적으로 array index이다. heap elements들은 heap operation동안 array내에서 위치를 바꾸기 때문에, heap element를 재위치시킬 때, 할 실제 구현은 또한 상응하는 프로그램 오브젝트에서 array index를 업데이트 시켜야 한다. application object들에 접근하는 세부사항은 크게 프로그램과 그것의 구현에 의존하기 때문에, 우리는 실제로 이러한 handles이 정확히 유지되어야 할 필요가 없다는 것을 주목하기 보다는 그것들을 여기에서 추구하지 않을 것이다.
이제 우리는 max-priority queue의 연산들을 어떻게 구현할지 이야기 한다. HEAP-MAXIMUM 절차는 Θ(1) 시간에 MAXIMUM 연산을 구현한다.
HEAP-MAXIMUM(A) 1 return A[1]
HEAP-EXTRACT-MAX 절차는 EXTRACT-MAX 연산을 구현한다. 그것은 HEAPSORT 절차의 for loo문(lines 3-5)와 유사하다.
HEAP-EXTRACT-MAX(A) 1 if A.heap-size < 1 2 error "heap underflow" 3 max = A[1] 4 A[1] = A[A.heap-size] 5 A.heap-size = A.heap-size - 1 6 MAX-HEAPIFY(A,1) 7 return max
HEAP-EXTRACT-MAX의 작동 시간은 O(lg(n))이다. 그것은 MAX-HEAPIFY를 위해 O(lg(n))의 시간 위에서 고정된 양의 작업을 하기 때문이다.
HEAP-INCREASE-KEY 절차는 INCREASE-KEY 연산을 구현한다. 배열에 들어가는 인덱스 i는 우리가 증가시키길 원하는 키의 우선순위 큐의 요소이다. 그 절차는 처음에 A[i]의 원소의 key를 그것의 새로운 값을 업데이트 시킨다. A[i]의 key를 증가시키는 것은 max-heap property를 위반하기 때문에, 그 절차는 그런 후에, Section 2.1의 INSERTION-SORT의 삽입 loop(lines 5-7)의 회상하는 방식으로, 새롭게 증가된 key를 위한 적절한 장소를 찾기 위해 이 노드부터 root까지 간단한 경로를 지나간다. HEAP-INCREASE-KEY가 이 경로를 지나갈 때, 그것은 반족으로 한 원소와 그것의 부모를 비교하고, 그것들의 키들을 교한하고, 그 원소의 키가 더 크다면 계속하고, 더 작다면 그만둔다. max-heap property가 이제야 유효하기 때문이다. (See Exercise 6.5-5 for a precise loop invariant.)
HEAP-INCREASE-KEY(A,i,key) 1 if key < A[i] 2 error "new key is smaller than current key" 3 A[i] = key 4 while i > 1 and A[PARENT(i)] < A[i] 5 exchange A[i] with A[PARENT(i)] 6 i = PARENT(i)
그림 6.5는 HEAP-INCREASE-KEY 연산의 한 예를 보여준다. n개의 요소를 가진 heap에서 HEAP-INCREASE-KEY 작동 시간은 O(lg(n))이다. line 3에서 업데이트 된 노드로부터 추적된 root로 가는 경로가 O(lg(n))이기 떄문이다.
MAX-HEAP-INSERT 절차는 INSERT 연산을 구현한다. 그것은 input으로서 max-heap A에 넣어질 새로운 원소의 key를 필요로 한다. 그 절차는 처음에 key가 -∞인 새로운 leaf를 트리에 더하여 max-heap을 확장한다. 그러고나서 이 새로운 노드의 KEY를 그것의 올바른 값으로 설정하고 max-heap property를 유지하기 위해 HEAP-ICREASE-KEY를 호출한다.
MAX-HEAP-INSERT(A,key) 1 A.heap-size = A.heap-size + 1 2 A[A.heap-size] = -infinity 3 HEAP-INCREASE-KEY(A, A.heap-size, key)
n개의 원소를 가진 heap에서 MAX-HEAP-INSERT의 작동시간은 O(lg(n))이다.
요약해서, 한 heap은 O(lg(n))시간에 사이즈가 n인 집합에서 어떤 priority-queue의 연산을 지원할 수 있다.
댓글 없음:
댓글 쓰기