Binary Heap

힙(heap)은 이진 힙(binary heap)이라고도 하며, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조입니다.

완전 이진트리(Complete Binary Tree) 이다.
부모노드의 키값과 자식노드의 키값 사이에는 대소관계가 성립한다.
키값 대소관계는 오로지 부모자식 간에만 성립되며 형제사이에는 대소관계가 정해지지 않았

Root node는 가장 끝(최대|최소)값이다. 항상자식노드는 부모노드보다 기준을따른다 (작거나, 크다)

특징

힙은 완전 이진트리입니다. 힙은 일반적으로 배열로 표현합니다. 루트 노드의 인덱스 i가 1인 경우 다음과 같은 속성이 있습니다.

노드 i의 부모노드 인덱스 : ⌊�/2⌋
노드 i의 왼쪽 자식 노드 인덱스 : 2*i
노드 i의 오른쪽 자식 노드 인덱스 : 2*i + 1
※왼쪽부터 한줄씩 센다

Heapify

heapify는 이진트리에서 힙 속성을 유지하는 작업을 합니다. 위에서 아래로 내려가면서 작업을 합니다.

요소 값과 자식 노드 값을 비교합니다.
만약 자식 노드 값이 크다면 왼쪽 오른쪽 자식 중 가장 큰 값으로 교환합니다.
힙 속성이 유지 될 때까지 1,2번 과정을 반복합니다.

e.g ) 우선순위 큐, Dijkstra 알고리즘, 힙 정렬