#7 트리(Tree) 2 - 힙(Heap)

1. 힙(Heap)

 힙은 최댓값, 최솟값의 탐색을 빠르게 하기 위해 고안된 완전 이진 트리를 기반으로 하는 자료구조이다.  

힙은 다음과 같은 조건을 만족한다.

• 어떤 노드 A의 키 값은 부모노드 B의 키 값과 대소관계를 가진다
• 형제노드 간에는 대소관계를 따지지 않는다.

 

2.  힙의 특징

• 부모노드의 키 값이 자식노드의 키 값 보다 항상 크다면 최대 힙, 항상 작다면 최소 힙이라고 한다.
• 최대 힙은 최댓값이, 최소 힙은 최솟값이 루트 노드가 되는 상태를 항상 유지한다.
• 힙의 종류에 따라 트리의 차수가 2보다 큰 경우도 있지만 대부분의 경우 힙이라고 하면 이진 힙을 가리킨다.
• 데이터의 삽입에 O(logN), 최댓값 혹은 최솟값 탐색에 O(1)의 시간복잡도를 보인다.
• 그 특성상 우선순위 큐 등의 자료구조를 구현하는데 사용할 수 있다.
• 정렬 알고리즘 중 하나인 힙 정렬에도 사용되는데, 내림차순 정렬에는 최대 힙을, 오름차순 정렬에는 최소힙을
  사용한다.
• 힙은 완전이진트리이기 때문에 일반적으로 배열로 구현된다. 루트노드의 인덱스는 0이며 어떤 노드의 인덱스가
  i일 때 왼쪽 자식노드는 i * 2 + 1, 오른쪽 자식노드는 i * 2 + 2 가 된다.

 

3. 힙의 연산(최소 힙 기준)

• 삽입(push)
  • 데이터를 배열의 맨 끝에 삽입한다.
  • 데이터가 삽입된 인덱스로부터 시작하여 부모노드가 존재하고 부모노드의 값이 자신보다 크다면
    부모 노드와 위치를 뒤바꾸는 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
• 삭제(pop)
  • 배열의 맨 끝의 데이터를 맨 처음의 데이터에 덮어씌운다.
  • 삽입과는 반대로 자신보다 값이 작은 자식노드가 있다면 자식노드와 위치를 뒤바꾼다.
    양측 자식노드 모두 자신보다 작다면 둘 중 보다 작은 쪽과 뒤바꾼다.
  • 위 작업을 더이상 위치변경이 발생하지 않을 때 까지 반복한다.
• 힙 변환(heapify)
  • 루트노드가 0이고 배열의 길이가 n인 힙이 아닌 배열을 힙으로 변환
  •  i = n//2-1 부터 탐색시작, 좌측 자식노드인 i * 2 + 1, 우측 자식노드인 i * 2 + 2 와 비교
  • 만약 자식노드중 자신보다 작은 것이 있다면 자식노드와 위치를 뒤바꾼다.
  • 위치변경이 발생했다면 위치를 바꾼 대상 인덱스를 기준으로 다시 탐색
  • 위치변경이 발생하지 않았다면 i-1을 탐색
  • i >= 0 일 동안 위 작업을 반복
• 힙 변환(heapify) 코드

from heapq import heappop


def heapify(arr, cur):
    # 좌, 우 자식노드
    left, right = cur * 2 + 1, cur * 2 + 2

    # 위치를 바꿀 대상 => 자기 자신으로 초기화
    target = cur

    # 좌측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 좌측 자식노드로 갱신
    if left < len(arr) and arr[left] < arr[target]:
        target = left

    # 우측 자식노드가 존재하고 현재 위치 변경 대상보다 키 값이 작을 경우
    # 위치 변경 대상을 우측 자식노드로 갱신
    if right < len(arr) and arr[right] < arr[target]:
        target = right

    # 자기 자신이 아닌 위치 변경 대상을 찾았다면
    # 위치를 변경하고 변경된 위치에 대해 heapify 재귀호출
    if cur != target:
        arr[cur], arr[target] = arr[target], arr[cur]
        heapify(arr, target)


# 힙이 아닌 배열
a = [1, 5, 2, 3, 7, 4, 6]

# len(a)//2-1 부터 0까지의 노드에 대해 heapify 호출
for i in range(len(a) // 2 - 1, -1, -1):
    heapify(a, i)

# 힙 출력
# 결과: [1, 3, 2, 5, 7, 4, 6]
print(a)

# 힙이 정상적으로 만들어졌는지 확인
# 결과: 1, 2, 3, 4, 5, 6, 7
for _ in range(len(a)):
    print(heappop(a), end=" ")

 => heapify 와 heappop 을 구현하는 것 만으로 힙 정렬을 구현할 수 있다.  heapify가 거의 O(N)에 가까운 성능을

      보이며 heappop 이 O(logN)의 성능을 보이기 때문에 힙 정렬은 N개의 데이터에 대해 O(NlogN)의 성능을 보인다.