힙 정렬

힙 구조

• 완전 이진 트리에 가까운 형태
• 이진 트리는 각 노드의 자식수가 2이하인 경우
• 완전 이진 트리는 Root 노드부터 Leaf 노드까지 빠짐없이 채워져 있는 트리

힙 특성

$A[PARENT(i)] \geq A[i]$

• 최대힙 특성
  • 부모 노드가 자식 노드보다 값이 항상 커야함
  • 전체 트리의 Root 노드 값이 가장 크다.
  • 각 하위 트리 구조의 Root 노드가 가장 큰 값을 가진다.

$A[PARENT(i)] \leq A[i]$

• 최소힙 특성
  • 부모 노드가 자식 노드보다 값이 항상 작아야함
  • 전체 트리의 Root 노드 값이 가장 작음
  • 각 하위 트리 구조의 Root 노드가 가장 작은 값을 가진다.

힙의 배열 저장 방식

• Root 노드는 배열의 첫번째 $A[1]$에 저장
• 각각의 노드들은 레벨별로 저장

$PARENT(i)$ - return 1/2 내림
$LEFT(i)$ - return 2i
$RIGHT(i)$ - return 2i+1

Root 노드로부터 트리의 높이

• $\theta(lgn)$
  Heap은 완전 이진트리 구조를 가지기 때문에 각 레벨마다 노드의 수가 2배씩 증가하므로

힙 특성

Max-Heapify

노드가 입력으로 주어졌을 때 노드의 좌 우 하위 트리들은 max-heap 특성을 유지하지만
노드의 값이 하위 트리 값보다 작거나 같아서 max-heap 특성을 만족하지 않을 때 max-heap 특성이 유지되도록 바꾸는 연산

힙 정렬 코드

• 주어진 배열을 힙 구조로 변경

def buildMaxHeap(A):
    heapsize = len(A)
    for i in range(heapsize // 2-1, -1, -1):
        heapify(A, i,heapsize)

def heapify(A, i,heapsize):
    leftChild = 2 * i +1
    rightChild = (2 * i) + 2
    if i < heapsize // 2:
        if A[leftChild] <= A[i] and A[rightChild] <= A[i]:
            return
        elif A[leftChild] > A[rightChild]:
            A[i], A[leftChild] = A[leftChild], A[i]
            heapify(A, leftChild,heapsize)
        elif A[rightChild] > A[leftChild]:
            A[i], A[rightChild] = A[rightChild], A[i]
            heapify(A, rightChild,heapsize)

• 최대갮 추출

?? 후술