자료구조 Heap(힙)이란?

- Heap이란..

힙은 최댓값 혹은 최솟값을 빠르게 찾기 위한 이진트리이다.

 

 

좌측 최소힙, 우측 최대힙

(이진 탐색 트리와는 다르게 힙 트리에서는 중복 값을 허용한다)

 

 

힙은 느슨한 정렬 상태(반정렬상태)를 유지하는데,
최소 힙의 경우 부모는 자식보다 작고, 최대 힙의 경우 부모는 자식보다 크다.

 

 

 

- 힙의 삽입, 삭제

 

힙의 삽입

새 요소를 힙의 마지막노드에 이어서 삽입하고
부모 노드와 비교하여 교환하는 형식으로 이루어진다.

 

힙의 삭제

힙의 루트에서 삭제 후 가장 마지막 노드를 루트 노드 자리로 바꿔준다.
이후에는 삽입때와 마찬가지로 부모 자식 노드를 비교해준다.

 

 

 

 

 

- 시간복잡도

 

 

힙의 삽입과 삭제는 힙의 높이만큼 O(logN)의 시간 복잡도를 갖고,

힙의 정렬의 시간 복잡도는 O(N*logN)이다. (전체 데이터 N * 삽입 시간 복잡도 logN)