[자료구조] 07. 힙 (Heap)

13 Oct 2019 in Computer-Science

힙 (Heap)의 정의와 특징에 대하여 알아보고 사용예시를 살펴본다.

1. 정의

힙은 다음의 두 가지 조건을 만족하는 형태의 트리이다.

1. 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입함 (완전 이진 트리)
2. 선택한 노드는 자식 노드가 가진 값보다 크거나 같음 (최소 힙일때는 반대)

2. 특징

데이터의 최대값이나 최소값을 탐색할때 탐색속도가 빠르다.

3. 시간 복잡도

• depth(h) 기준 : O(h)
• 노드의 개수(n) : O(logn)