힙

• 힙은 기본적으로 완전 이진 트리(Complete Binary Tree)를 기본으로 한 자료 구조

• 부모 노드와 자식 노드 간의 대소관계가 성립하는 자료 구조

• 힙의 루트 노드는 힙 내의 데이터들 중 가장 큰 값이거나 가장 작은 값

힙은 왜 쓰는가

• 최대 값이 최소 값에 빠르게 접근 하고 싶어서
• 최대 값이나 최소 값 데이터 접근은 정렬만 해놓으면 링크드 리스트, 배열, 힙 큰 차이 없다
• 힙은 데이터를 추가 할 때 유리하다
  • 배열이나 링크드 리스트는 재정렬의 과정이 필요하다 O(n)의 시간복잡도
  • 힙은 새로추가된 노드의 부모노드들과만 비교해도 정렬 상태를 유지 할수 있어서 O(logn)의 시간복잡도
  • 정렬해야할 데이터가 많을수록 힙은 유리하다

완전 이진 트리는 배열로 구현하는게 더 효율적이다

• 완전 이진 트리는 왼쪽부터 채워나간다
• 각 계층마다 만들어질수 있는 노드 개수가 정해져 있기 때문에 index 확인이 가능하다
  • 해당 레벨의 최대 노드 개수 = 2^레벨 - 1
  • 원하는 노드가 있으면 n-1 레벨 까지 최대 노드 개수 + n 레벨에서 몇 번째 만 해주면 바로 구함
• 트리가 기울어 지지 않아서 배열 가운데 empty 가 발생 안한다

힙과 완전이진 트리의 차이

• 힙은 부모와 자식 노드 간의 대소관계가 성립되어야 한다는 조건이 있기 때문에, 삽입 및 삭제 후 노드를 다시 정렬해주는 기능이 추가로 필요하다

구현

• 추가 시에는 맨 아래 레벨 맨 마지막 노드에 추가되는데 여기서부터 부모와 비교를 통해서 스왑하면서 올라나간다 (버블 업)
• 루트에서 값 빼올 때 시에는 맨 마지막 노드를 루트 노트로 올린다음 자식들과 비교를 통해서 스왑하면서 내려나간다 (트릭클 다운)

최소 값과 최대 값을 빠르게 찾을 수 있게 도와주는 힙(Heap)