3. 힙 정렬 (Heap Sort)

insertItem, removeMin 함수가 $O(\log n)$의 시간복잡도를 갖는 힙으로 구현된 우선순위 큐를 사용하면, $n$개의 원소를 갖는 리스트를 $O(n\log n)$시간에 정렬할 수 있다.

이는 $O(n^2)$ 시간이 걸리는 선택정렬이나 삽입정렬에 비해 훨씬 빠른 속도이다.

def heapSort(L):
	H = Heap()
    while !L.isEmpty():
    	k=L.removeFirst()
        H.insertItem(k)
    while !H.isEmpty():
    	k=H.removeMin()
        L.addLast(k)
    return L

2차 정렬과 힙 정렬의 시간 복잡도 비교

힙 정렬의 개선

• 제자리 힙 정렬은 힙 정렬의 공간 복잡도를 줄일 수 있다.
• 상향식 힙 생성은 힙 정렬의 속도를 높일 수 있다.

제자리 힙 정렬

정렬할 리스트가 배열로 주어진 경우에 사용할 수 있다. 힙을 저장하는데 정렬할 리스트 $L$을 사용하여, 공간 사용량을 줄인다.

지금까지 사용한 최소힙^min-heap 대신, 최댓값이 루트 노드로 가는 최대힙^max-heap을 사용한다.

def inPlaceHeapSort(A): # input array A of n keys
	buildHeap(A)
    for i in range(n, 1, -1): # n downto 2
    	swap(A[1],A[i])
        downHeap(1, i-1)
    return A
def buildHeap(A):
	for i in range(1, n+1): # 1 to n
            insertItem(A[i])
    return A
def downHeap(i, last): # index i of A representing a maxheap of size last
	left = 2*i
    right = 2*i+1
    if left>last:
    	return
    greater=left
    if right<=last:
    	if key(A[right])>key(A[greater]):
        	greater=right
    if key(A[i])>=key(A[greater]):
    	return
    swap(A[i], A[greater])
    downHeap(greater, last)

배열 $A$에서, 첨자 $i$의 왼쪽 부분은 힙을 정렬하는데 쓰이고, 오른쪽 부분은 배열을 저장한다.

먼저, 배열을 최대힙으로 만들어준다. 이후, 배열의 오른쪽부터 힙에서 최댓값을 꺼내어 넣어준다. 힙에서 값을 꺼낸 후, downHeap()을 수행하여 힙 순서를 복구해주고 다시 최댓값을 꺼내는 작업을 반복하며 정렬을 할 수 있다.

상향식 힙 생성

기존에는 $n$회의 연속적인 inserItem() 함수를 이용하여 $O(n \log n)$시간에 힙을 생성했다. 대안으로, 만약 힙에 저장되어야 할 모든 키들이 미리 주어진다면 $O(n)$시간만에 힙을 생성하는 상향식 힙 생성을 사용할 수 있다.

def buildHeap(L):
    T=CompleteBinaryTree(L)
    T=rBuildHeap(T.root())
    return T
def rBuildHeap(v):
	if isInternal(v):
    	v.left=rBuildHeap(leftChild(v))
        v.right=rBuildHeap(rightChild(v))
        downHeap(v)
	return v

단계 $i$에서, 각각 $2^i-1$개의 키를 가진 두 힙을 $2^{i+1}-1$개의 키를 가진 힙 하나로 합병한다.

두 개의 힙과 키 $k$가 주어졌을때, 키 $k$를 루트로 갖는, 두 힙을 부트리로 갖는 트리를 생성하고 downHeap()을 수행하여 힙순서 속성을 복구해주어 두 트리를 병합할 수 있다.

rBuildHeap의 각 재귀호출이 힙인 부트리를 반환하는 방식으로, 외부노드에서부터 진행되어 상향식이라 부른다.

비재귀적 상향식 힙 생성

정렬할 리스트가 배열로 주어졌을 때 사용.

def buildHeap(A):
	for i in range(n//2, 0, -1): # n//2 downto 1
    	    downHeap(i, n)
    return