[자료 구조 #9] 힙(heap)

기회는 준비된 자에게 온다 !

힙의 개념

힙(heap)은 완전 이진 트리의 한 종류다.

노드에 저장된 데이터 중 최대값과 최소값을 빨리 탐색하기 위한 자료구조이며 반정렬 상태다.

또한 힙 트리는 중복된 값을 허용한다.

추가로 힙은 우선순위 큐를 위해 만들어진 자료구조이다.

우선 순위 큐(Priority Queue)란?

우선 순위의 개념을 큐에 대입한 자료구조로써 우선 순위가 높은 데이터가 먼저 나간다.

힙의 종류

힙에는 두 가지 종류가 있다

• 최소 힙(Min Heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

• 최대 힙

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

힙 사용 예시

최댓값이나 최솟값을 빠르게 탐색해야 하는 경우 사용됨!

• 우선순위 큐
• 최단 경로 알고리즘

Reference

• [자료구조] Heap(힙) - 개념, 종류, 활용 예시, 구현