자료구조 : 힙(Heap)

힙(Heap)

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)

• 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

 

힙(Heap)을 사용하는 이유

• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림
• 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸림
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

 

힙(Heap)의 구조

• 힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류할 수 있음
• 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
• 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
• 완전 이진 트리 형태를 가짐

 

힙(Heap)과 이진 탐색 트리

• 공통점 : 힙과 이진 탐색 트리는 모두 이진 트리임
• 차이점 : 
      - 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
      - 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
      - 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

 

힙에 데이터 삽입 - 기본 동작

• 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입

Max Heap의 경우(삽입할 데이터가 힙의 데이터보다 클 경우)

• 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
• 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함(swap)

 

Max Heap의 경우(힙의 데이터 삭제)

• 삭제는 최상단 노드 (root노드)를 삭제하는 것이 일반적임
  - 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서 최대값과 최소값을 꺼내 쓸 수 있도록 하는 것임
• 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드(일반적으로 가장 마지막에 추가한 노드)를 root 노드로 이동
• root 노드의 값이 child node보다 작을 경우 root노드의 child node중 가장 큰 값을 가진 노드와 root노드 위치를 바꿔주는 작업을 반복함(swap)

 

힙과 배열

• 일반적으로 힙 구현시 배열 자료구조를 활용함
• 배열은 인덱스가 0번부터 시작하지만 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 수월함
  - 부모 노드 인덱스 번호(parent node's index) = 자식 노드 인덱스 번호(child node's index) // 2
  - 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호(parent node's index) * 2
  - 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

# 10 노드의 부모 노드 인덱스
2 // 2 
# 1출력

# 15 노드의 왼쪽 자식 노드 인덱스 번호
1 * 2
# 2출력

# 15 노드의 오른쪽 자식 인덱스 번호
2 * 2 + 1
# 5출력