Heap

Heap

• Complete binary tree의 하나이다.
• 여러 값들 중에서 최대값(max heap)이나 최솟값(min heap)을 빠르게 찾도록 하는 자료구조이다.

max heap

• 부모 노드의 키 값이 자식 노드의 값보다 크거나 같은 complete binary tree

min heap

• 부모 노드의 키값이 자식 노드의 키 값보다 작거나 같은 complete binary tree

heap 구조

• 왼쪽 자식의 index = 부모 index * 2
• 오른 자식의 index = 부모 index * 2 + 1
• 부모 index = 자식 index // 2

heap 삽입

• 마지막 노드에 새로운 노드를 추가
• 새로운 노드와 부모 노드의 값을 비교하고 더 클경우 교환

heap 삭제

• max heap에서 root 노드가 최대값이므로 삭제
• 가장 마지막 노드를 root 노드로 갖고옴
• 자식들과 비교해서 더 큰것과 교환