힙 : 완전 이진 트리로, 최대 힙(부모>자식 : 부모가 최대값) 또는 최소 힙(부모<자식 : 부모가 최소값)이 있으며, 이진 힙(Binary Heap)이라고도 한다.
- 힙은 형제 노드 간의 규칙이 없으며, 부모와 자식의 크기 비교만 있기 때문에 자식으로 들어오는 순서는 왼쪽, 오른쪽 순서로 들어오게 된다.
- 배열로 구현
- 왼쪽 자식 인덱스 = 부모인덱스*2
- 오른쪽 자식 인덱스 = 부모인덱스*2+1
최소 힙 (min heap)
부모 노드 값 < 자식 노드 값 : 루트가 최솟값
최대 힙 (max heap)
부모 노드 값 > 자식 노드 값 : 루트가 최댓값
Heapify
: insert 또는 delete 연산 수행 시 heap의 속성을 유지하기 위한 과정
heap의 속성에 따라 부모와 자식 간의 값 비교를 통해 heap에 위배되면 값을 바꿔주며 heap의 속성이 만족할 때까지 반복한다.
get, insert, delete : O(logn), 전체 정렬 O(nlogn)
