heap

최악의 경우에 시간복잡도는 O(nlog2n)

heap은 2가지 조건을 만족한다.

1. complete binary tree

2. heap property를 만족해야 함.

- max heap property : 부모 노드 값 >= 자식

- min heap property : 부모 노드 값 <= 자식

 

full binary tree는 모든 레벨에 노드들이 꽉 차 있다. full binary tree는 complete binary tree를 포함.

complete binary tree는 마지막 레벨에 몇 개의 노드가 비어있는 트리.

 

힙은 일차원 배열로 표현 가능함.

루트 노드는 A[1]이다.

A[i]의 부모는 A[i/2]

A[i]의 왼쪽 자식은 A[2i], 오른쪽 자식은 A[2i+1]

 

# 힙 정렬

max heap은 작은 값을 가진 노드의 왼쪽과 오른쪽 자식 중 더 큰 자식과 자리를 바꾸는 방식으로 정렬.