1. 힙

아래 특성을 가진 이진 트리
i) 구조적 성질 : 완전이진트리
ii) 힙 성질 : 모든 노드의 값은 자식 노드의 값보다 크거나 같다(최대힙)
또는 자식 노드의 값보다 작거나 같다(최소힙)

1-1. 힙 형태

• n개 노드를 가진 힙의 높이 = ⌊log n⌋
• n개 노드를 가진 힙의 리프 노드 수 = ⌈n/2⌉

1-2. 배열로 힙 구현

i가 특정 노드의 인덱스일때

• 왼쪽 자식 노드 인덱스 = 2*i+1
• 오른쪽 자식 노드 인덱스 = 2*i+2
• 부모 노드 인덱스 = ⌊(i-1)/2⌋

1-3. Rebuild Heap(최대힙)

• 양쪽 부트리가 힙일때 루트를 포함해 힙으로 재구성
• 시간복잡도 : O(h) = O(log n). 각 레벨마다 이동하며 값을 비교

예시)

알고리즘

def getLeftChild(index, n):
    left_child = 2 * index + 1
    
    if left_child < n:
        return left_child
    return None
    
def getRightChild(index, n):
    right_child = 2 * index + 2
    
    if right_child < n:
        return right_child
    return None

def rebuildHeap(heap, root, n):
    current = root
    value = heap[root]
    left_child = getLeftChild(current, n)
    while (left_child):
        right_child = getRightChild(current)
        larger_child = left_child
        if (right_child and heap[right_child] > heap[left_child]):
            larger_child = right_child
            
        if value < heap[larger_child]:
            heap[current] = heap[larger_child]
            current = larger_child
        else:
            heap[current] = value
            break

---

2. 힙 정렬(최대힙)

힙을 이용한 정렬 방법

1단계) 최대 힙 만들기

리프 노드가 아닌 노드를 찾아 상향식으로 rebuildHeap
알고리즘

n = len(heap)
# (n-1)-1//2 = 마지막 노드의 부모
for i in range((n-1)-1//2, -1, -1):
    rebuildHeap(heap, i, n)

2단계) 루트를 빼면서 정렬

다음 과정을 반복해 정렬한다
1) 루트 노드와 마지막 노드를 교환한다
2) 힙 크기를 1 줄인다. rebuildHeap 한다
3) 루트 노드가 유일한 노드가 될 때까지 반복한다

최대힙의 루트는 최대 값이므로 오름차순으로 정렬된다

알고리즘

heap_size = n
root = 0
for last in range(n-1, 0, -1):
    tmp = heap[root]
    heap[root] = heap[last]
    heap[last] = tmp
    
    heap_size -= 1
    rebuildHeap(heap, root, heap_size)

전체 코드

def heapSort(heap):
    # 1단계
    n = len(heap)
    last_parent = ((n-1)-1)//2
    for i in range(last_parent, -1, -1):
        rebuildHeap(heap, i, n)
    
    # 2단계
    heap_size = n
    root = 0
    for last in range(n-1, 0, -1):
        tmp = heap[root]
        heap[root] = heap[last]
        heap[last] = tmp
        heap_size -= 1
        rebuildHeap(heap, root, heap_size)

힙 정렬의 시간복잡도

rebuildHeap() 시간복잡도

• 힙 레벨마다 비교하며 교체 : O(log n)

1단계 시간 복잡도

• 힙에서 리프노드가 아닌 노드의 수는 대략 n/2
• rebuildHeap()은 n/2번 실행
• tight bound : O(n)

2단계 시간 복잡도

• n-1번 rebuildHeap()을 실행함 : O(n log n)

전체 시간 복잡도

• O(n log n)

---

3. 우선순위 큐

힙을 사용하는 대표적인 예

• 우선순위 큐 : 각각 키값을 가지는 원소들의 집합을 관리하는 자료구조
• 효율적인 삽입, 최대키 찾기, 최대키 삭제 연산 지원
• 사용 예: 우선순위로 정리된 OS의 프로세스 리스트(매우 동적)

3-1. 삽입 연산

• 힙의 마지막 노드로 삽입
• 삽입 값이 부모보다 크면 교체 반복
• W(n) : O(log n)

알고리즘

def insert(heap, key):
    heap_size += 1
    i = heap_size-1
    while i > 0 and heap[Parent(i)] < key:
        heap[i] = heap[Parent(i)]
        i = Parent(i)
    heap[i] = key   

3-2. 최대키 원소 삭제 연산

• 루트 키를 반환하도록 저장
• 마지막 노드를 루트로 이동
• rebuildHeap 실행

알고리즘

def deleteMax(heap):
    max = heap[0]
    heap[0] = heap[last]
    heap_size -= 1
    rebuildHeap(heap, 0, heap_size)
    return max

• 수행시간 : O(log n)

3-3. heapq

• 파이썬의 힙 우선순위큐 라이브러리 (최소힙)
• heapq.heappush(heap, item) : 삽입
• heapq.heappop(heap) : 최소키 삭제
• heapq.heappushpop(heap, item) : 삽입 후 최소키 삭제
• heapq.heapify(h) : 리스트 h를 힙으로 만듬