완전이진트리

• 왼쪽부터 차례로 빈 곳 없이 채워진 이진트리
• 인덱스 표시 가능

index	1	2	3	4	5	6
-	3	2	4	5	0	1

규칙

• 모든 노드의 부모 노드 인덱스 번호는 2로 나눈 몫
• 모든 노드의 왼쪽 자식은 본인 인덱스 2, 오른쪽 자식은 본인 인덱스 2 + 1

포화 이진트리

• 모든 트리 레벨에서 노드가 꽉 차 있는 이진트리
• 노드의 총 차수 : n일 때,
  • 노드의 총 개수 : 2^n-1개

힙 자료구조

• 완전이진트리 기반 자료구조

최소힙

• 완전이진트리 + 어떤 서브트리를 보더라도 부모 노드는 항상 자식 노드보다 작아야 한다.
  • 자식 노드가 항상 부모 노드보다 커야 한다.

최소힙 삽입

1. 완전이진트리 유지 + 맨 끝에 넣음
2. 최소힙 유지 ➡️ 조상 노드를 거슬러 올라가며 부모가 더 큰 경우 스왑

최소힙 삭제

1. 루트노드 확보(최솟값) + 맨 뒤에서 잘라 올림
2. 루트로 맨 뒤 값을 잘라 올린 후 최소힙 요건 만족하는지 확인
3. 자식 노드의 숫자가 더 작으면 왼쪽 / 오른쪽 자식 중 작은 수를 택해 리프 노드가 될 때까지 스왑

heap = [0]


def heap_push(item):
    heap.append(item)

    child = len(heap) - 1
    parent = child // 2

    while parent > 0 and heap[parent] > heap[child]:
        heap[parent], heap[child] = heap[child], heap[parent]
        child = parent
        parent = child // 2


def heap_pop():
    if len(heap) == 1:  # 힙에 아무 값이 없는 경우
        return 0

    result = heap[1]  # 루트 저장
    heap[1] = heap[-1]  # 제일 마지막 값 루트에 저장
    heap.pop()

    parent = 1
    child = parent * 2  # 인덱스 0부터 시작하므로 +1, 우선 좌측을 기준

    while child < len(heap):
        if child + 1 < len(heap) and heap[child] > heap[child + 1]:  # 우측 자식이 존재 + 좌측 > 우측
            child += 1  # 기준 우측으로 변경

        if child >= len(heap) or heap[parent] <= heap[child]:
            break

        heap[parent], heap[child] = heap[child], heap[parent]
        parent = child
        child = parent * 2

    return result

최대힙

• 완전이진트리 + 어떤 서브트리를 보더라도 부모 노드는 항상 자식 노드보다 커야한다.