[Data Structure] Heap

Heap

• Complete Binary Tree
  ※ 위에서 아래로 왼쪽에서 오른쪽으로 노드들이 채워져 있는 트리
  
• 최대 힙(Max Heap)과 최소 힙(Min Heap)이 존재
  ※ 루트 노드의 값이 최댓값이면 Max Heap / 최솟값이면 Min Heap 이다.
  
• 루트 노드에는 항상 최댓값 or 최솟값이 있으므로 탐색할 때 O(1)의 시간이 걸린다.
• 루트 노드를 제거 후, Heap 구조를 유지하기 위해 Heapify의 과정은 O(logN)의 시간이 걸린다.
  

삽입

1. 현재 삽입할 노드를 힙의 마지막에 추가한다.
2. 부모 노드와 비교를 진행하여 힙 성질을 만족시킨다.

삭제

1. 루트 노드를 제거한 후, 힙의 맨 마지막에 존재하는 노드를 루트 노드에 가져온다.
2. 자식 노드와 비교를 하며 힙 성질을 만족시킨다.

참고

• 이진 힙(Binary Heap)
• interview_question_for_beginner
• [자료구조] 힙(heap)
• [자료구조] 힙(heap)이란