[자료구조] 힙이란?(heap)

힙이란?

• 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조
• 키값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는 느슨한 정렬상태.
• 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
  
• 중복값을 허용한다.(이진 탐색트리와는 다름.)
• 우선순위 큐, 허프만정렬, 힙정렬 등에서 사용 

 

힙의 종류

1. 최대힙(Max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)

2. 최소힙(Min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)

-> 완전 이진트리 : 마지막 레벨을 제외하곤 완전히 꽉 찬 상태이고, 마지막 레벨의 맨 왼쪽부터 꽉 차 있어야함.

 

 

힙의 구현

• 힙은 논리적 자료구조로 물리적으로는 보통 배열을 이용해 구현
• 구현 편의를 위해 배열의 0번인덱스는 비워둠
• 힙의 삽입은 힙 정렬(heap sorting), 힙의 삭제는 heapify를 사용함.
• 힙의 표현
  • 루트노드 A[1]
  • A[i]의 부모노드 A[i/2]
  • A[i]의 왼쪽노드 A[2i]
  • A[i]의 오른쪽노드 A[2i + 1]

 

heapify

• 트리의 전체모양은 완전 이진트리.
• 왼쪽, 오른쪽 부트리는 완전 그 자체로 힙
• 유일하게 root만이 힙이 아닐 때
• max heapify와 min heapify는 부호만 반대로

max heapify

1. 루트를 기준으로 자식노드중 큰 값과 자리를 바꿈.(없을경우 왼쪽,오른쪽의 부트리는 힙이기 때문에 정렬완료.)

2. 자리를 바꾼 방향의 부트리에서 자리 변경이 안 일어 날 때 까지 1번을 반복함.

 

 

힙정렬

• 배열을 힙을 만들기 위해 힙정렬을 함.
• 배열<->트리 논리적 구조로 생각하여 배열을 완전이진트리로 만든다
• 맨 마지막 리프노드의 부트리부터 heapify진행.(그림의 7을 루트노드 16부터 진행)

  

  

   

힙의 삽입

• 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다.
• 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.(힙정렬 참조)

힙의 삭제

• 힙의 루트와 맨 마지막값을 바꿈.
• 힙의 크기를 1줄인다.
• 힙의 루트로 heapify진행.