[자료구조] 힙 Heap

힙(Heap)

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
  • 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
• 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)의 시간복잡도 소요, 이에 반해 힙은 O(logn) 소요
• 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용

 

힙 구조

출처: 위키백과

• 최대값을 구하기 위한 구조(최대 힙, Max Heap)와 최소값을 구하기 위한 구조(최소 힙, Min Heap)로 분류 할 수 있음
• 힙의 두 가지 조건
  1. 각 노드의 값이 최대 힙의 경우 해당 노드의 자식 노드가 가진 값보다 크거나 같고, 최소 힙의 경우 작거나 같아야 함
  2. 완전 이진 트리 형태

힙과 배열

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

 

힙 동작

데이터 삽입하기 - 기본

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

 

데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보가 클 경우(최대 힙의 예시)

1) 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐

2) 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap)

 

 

 

힙의 데이터 삭제하기(최대 힙의 예시)

1) 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임

• 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것

2) 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동

3) root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)

 

힙(Heap) vs 이진 탐색 트리(Binary Search Tree)

 

	힙(Heap)	이진 탐색 트리(Binary Search Tree)
공통점	• 이진 트리
차이점	• 각 노드의 값이 자식 노드보다 크거나/작거나(최대 힙/최소 힙) 같음 • 이진 탐색 트리의 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건 없음 • 최대/최소값 검색을 위한 구조	• 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼 • 탐색을 위한 구조