2. 힙 (Heap)

힙

힙은 내부노드에 키를 저장하며, 다음 두 가지 속성을 만족하는 이진트리이다.

• 힙 순서(Heap Order): 루트노드를 제외한 모든 내부노드 $v$에 대해, $\text{key}(v)\geq \text{key}(\text{parent}(v)) $
• 완전 이진 트리: 힙의 높이를 $h$라 하면, 
  • $i=0, \cdots h-1$에 대해, 깊이 $i$인 노드가 $2^i$개 존재
  • 깊이 $h-1$에서, 내부노드들은 외부노드의 왼쪽에 존재

힙의 마지막 노드는, 깊이 $h-1$의 가장 오른쪽 내부노드이다.

힙의 높이

$n$개의 키를 저장하는 힙의 높이는 $O(\log n)$이다.

깊이 $i=0, 1, 2, \cdots , h-2 $에 $2^i$개의 키, 그리고 깊이 $h-1$에 적어도 한 개의 키가 존재하므로 $n\geq 2^{h-1}$, 즉 $h \geq \log n + 1$

힙과 우선순위 큐

힙을 사용하여 우선순위 큐를 구현할 수 있다. 이때, 마지막 노드의 위치를 관리하게 된다.

insertItem

힙을 사용한 우선순위 큐에 원소를 삽입할 때, 세 단계를 거친다.

1. 삽입 노드 z, 즉 새로운 마지막 노드를 찾는다.
2. 새로운 아이템 k를 z에 저장한 후, expandExternal(z)를 활용하여 z를 내부노드로 확장한다. (z아래 빈 자식 노드를 만든다.)
3. 힙순서 속성을 복구한다.

def insertItem(k):
	advanceLast()
	z = lastNode(T)
    z.item = k
    expandExternal(z)
    upHeap(z)

upHeap

힙순서 속성을 복구하기 위해 upHeap을 사용한다.

자식노드와 부모노드를 비교하여, 부모노드보다 자식노드의 키 값이 작을 경우 두 노드를 swap 한다. 이를 루트노드까지 반복한다.

힙의 높이가 $\log n$이므로, 시간복잡도는 $O(\log n)$이 된다.

def upHeap(z):
	if isRoot(z):
    	return
    if key(z)>=key(parent(z))
    	return
    swap(z, parent(z))
    upHeap(parent(z))

removeMin

힙에서 최소키값을 갖는 원소는 루트 노드에 저장된다.

removeMin 알고리즘은 세 단계로 진행된다.

1. 루트 키를 마지막 노드 w의 키로 대체
2. reduceExternal을 통해 w와 그 자식들을 외부노드로 축소
3. 힙순서 속성 복구

def removeMin():
	k = key(root())
    w = last()
    setRoot(w)
    retreatLast()
    z = rightChild(w)
    reduceExternal(z)
    downHeap(root())
    return k

downHeap

downHeap 알고리즘은 루트로부터 하향 경로를 따라가며 힙순서를 복구한다. 이 역시 upHeap과 유사하게 $O(\log n)$에 실행된다.

def downHeap(v):
	if isExternal(leftChild(v)) and isExternal(rightChild(v)):
    	return
    smaller = leftChild(v)
    if isExternal(rightChild(v)):
    	if key(rightChild(v)) < key(smaller):
        	smaller = rightChild(v)
    if key(v) <= key(smaller):
    	return
    swap(v, smaller)
    downHeap(smaller)

마지막 노드 갱신

삽입/삭제를 위한 노드를 찾는 알고리즘

def advanceLast(v):
	while isRight(v):
    	v=parent(v)
    while isLeft(v):
    	v=brother(v)
    while isInternal(v):
    	v=leftChild(v)
def retreatLast(v):
	while isLeft(v):
    	v=parent(v)
    while isLeft(v):
    	v=brother(v)
    while isInternal(v):
    	v=rightChild(v)

배열을 이용한 힙 구현

$n$개의 키를 가진 힙을 크기 $n+1$의 배열로 표현 가능하다. 첨자 0 셀은 사용하지 않는다.

첨자 $i$에 존재하는 노드에 대해, 왼쪽 자식은 $2i$에 존재하고, 오른쪽 자식은 $2i+1$에 존재한다. 부모는 $i/2$에 존재한다.

노드 사이의 링크, 외부노드 등을 표현할 필요가 없어 편리하다.

insertItem은 항상 첨자 $n+1$에서 작업하고, removeItem은 항상 첨자 $n$에서 작업하면 된다. 즉, advanceLast 등의 함수가 필요없어진다.