HEAP

 

Heap이란 용어는 본래 힙정렬로부터 나온 말이다. 

프로그래밍 언어가 제공하는 공간개념인 Heap 역시 이 자료구조에서 유래한 표현이다. 

 

Heap 자료구조란 complete binary tree를 배열로 구현한 형태의 자료구조를 의미한다.

complete binary tree를 기반으로 하기 때문에 원소의 갯수가 n인 heap의 높이는 O(log n)이다. 

 

ary의 index 1부터 배열을 채우기 시작한다. 

부모, 자식노드는 일반적으로 다음 매크로/인라인을 통해 구현한다

#define PARENT(i) (i>>1)
#define LEFT(i) (i<<1)
#define RIGHT(i) (i<<1)|1

 

배열 내의 원소의 개수는 A.length로 배열 A의 원소 중 힙에 속하는 원소의 개수를 A.heap-size로 표기한다.A.length와 A.heap-size가 다를 수 있다. 즉, 배열 내의 10개의 원소가 들어있을 수 있지만, 7번째 이후 원소들은 힙 내의 원소들이 아닐 수 있다. 

 

모든 설명은 max heap기준으로 한다. 

max heap에서 가장 큰 값은 루트노드에 저장된다.

한 노드의 자식노드들에는 해당 노드의 값보다 작은 값들이 저장된다. 

 

 

 

max heap을 구현에 필요한 함수들을 살펴본다.

1. max_heapify --- O(log n)

max_heapify는 위치 i의 노드를 자신의 자식노드드로가 비교해가며 해당 노드를 max heap의 특성에 부합하는 위치로 '내려보낸다'.

max_heapify(A,i)
	l=LEFT(i)
    R=RIGHT(i)
    
    largest=i
    if l<=A.heap-size and ary[i]<ary[l]
    	largest=l
    if r<=A.heap-size and ary[largest]<ary[r]
    	largest=r
    
    if largest!=i
        SWAP(ary[i],ary[largest])
        max_heapify(A,largest)

1-1. max_heapify_non_recur --- O(log n)

max_heapify_non_recur(A,i)
	while i>=PARENT(A.heap_size)
        l=LEFT(i)
        r=RIGHT(i)
        largest=i
        
        if ary[i]<=ary[l]
        	largest=i
        if ary[largest]<=ary[r]
        	largest=r
        
        if largest!=i
            SWAP(ary[i],ary[largest])
            i=largest
        else break

 

2. 힙 생성: build_max_heap() --- O(n)

주어진 배열내의 원소를 max heap으로 재배치한다.

build_max_heap(A)
	A.heap-size=A.length
	for i=A.length/2 down to 1
    	max_heapify(A,i)

 

n개의 원소를 log n씩 수행하기에 O(nlogn)처럼 보일 수 있으나, 이 함수의 수행시간은 O(n)이다. 

(Introduction to Algorithms Thrid Edition 161p)

힙의 응용

힙 자료구조는 다양한 분야에 응용이 가능하다.

1. 힙 정렬: heap_sort() ---O(n log n)

A[1~A.length]까지의 원소를 오름차순으로 정렬한다.

heap_sort(A)
	build_max_heap(A)
    for i=A.heap-size down to 2
		SWAP(ary[1],ary[i])
		A.heap_size--
        max_heapify(A,1)

max힙의 루트, 즉 가장 큰 원소와 배열의 마지막 원소를 교환환 후, heap-size를 줄인다. 

이후, max_heapify를 실행하면 줄어든 heap-size만큼의 max heap이 만들어지게된다. 

이 과정을 반복하여 최종적으로 배열을 오름차순으로 정렬한다. 

 

2.우선순위 큐

다음 함수들을 사용해 heap으로 우선순위 큐를 구현할 수 있다.

2-1. maximum() --- O(1)

heap 내의 가장 큰 원소를 리턴한다

heap_maximum(A)
	return A[1]

2-2. extract_max() --- O(log n)

heap 내의 값이 가장 큰 원소를 제거한다.

heap_extract_maximum(A)
	if(A.heap_size<1)
    	error "empty heap"
    
    max=A[1]
    
    A[1]= A[A.heap-size]
	A.heap-size--
    max_heapify(A,1)
    
    return max

 

2-3. increase_key() --- O(log n)

heap 내의 특정 위치의 값을 증가시킨다.

heap_increase_key(A,i,key)
	if(ary[i]>=key)
    	error "현재 값보다 더 큰 값으로 변경해야한다"
    
    while i>1
    	if key>ary[PARENT(i)]
        	ary[i]=ary[PARENT(i)]
            i=PARENT(i)
		else break

    ary[i]=key

2-4. insert() --- O(log n)

heap 내에 원소를 추가한다

max_heap_insert(A,key)
	A.heap-size++
    
    ary[A.heap-size]= -INF
    heap_increase_key(A,A.heap-size,key)