[자료구조] 힙 (heap)

힙 이란?

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
  • 완전 이진 트리? 노드를 삽입할때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리
• 힙을 사용하는 이유
  • 배열에 데이터를 넣고, 최소값과 최대값을 찾는 시간 = O(n)
  • 힙에 데이터를 넣고, 최소값과 최대값을 찾는 시간 = O(logn)
  • 우선순위큐와 같이 최대값/최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용

 

힙 구조

• 힙은 최대힙(최대값을 구하기 위한 구조, Max Heap)과 최소힙(최소값을 구하기 위한 구조, Min Heap)으로 분류
• 힙은 두가지 조건을 가지고 있는 자료구조다
  1. 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(이게 최대힙)
  2. 완전 이진 트리의 구조를 가진다

 

힙과 이진 탐색 트리

• 공통점 : 둘다 이진 트리
• 차이점
  • 힙 : 각 노드의 값이 자식노드보다 크거나 같다 (최대힙)
  • 힙 : 왼쪽, 오른쪽 자식 노드의 값은 오른쪽이 클수도, 왼쪽이 클수도 있다
  • 이진 탐색 트리 : 값 크기는 왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드
• 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대값/최소값 검색을 위한 구조다

 

힙 동작

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

• 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워짐

힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우

• 먼저, 삽입된 데이터는 왼쪽 최하단부 노드부터 채워짐
• 부모노드보다 값이 클 경우, 부모노드와 위치를 바꿔주는 작업을 반복

힙의 데이터 삭제하기

• 보통 삭제는 최상단 노드(root node)를 삭제하는것이 일반적!
  • 힙의 용도는 최대값/최소값을 root에 놓아서 바로 꺼내서 쓸 수 있도록 하는거니까
• 최상단 노드 삭제 -> 가장 최하단부 왼쪽에 위치한 노드(가장 마지막에 추가한 노드)를 root로 이동
• root노드의 값이 자식노드보다 작을 경우, root의 자식노드 중 가장 큰값을 가진 노드와 root의 위치를 바꿔주는 작업을 반복