힙(Heap)

힙은 크게 두가지로 나뉩니다.

 

1. 메모리 할당에서의 힙: 컴퓨터 프로그래밍에서 "힙"은 동적으로 할당된 메모리 영역을 의미합니다. 이 메모리 영역은 정적인 스택과 대조되며, 필요에 따라 프로그램에서 동적으로 할당 및 해제됩니다. 힙은 주로 동적으로 크기가 변하는 데이터 구조를 저장하기 위해 사용됩니다. 예를 들어, 배열, 연결 리스트, 트리 등의 자료구조는 힙에 저장될 수 있습니다.
2. 우선순위 큐에서의 힙: 힙은 이진 트리로 구현되는 자료구조로, 우선순위 큐를 구현하는 데 사용됩니다. 이진 힙은 보통 "최소 힙(Min Heap)" 또는 "최대 힙(Max Heap)"으로 분류됩니다. 최소 힙은 부모 노드가 자식 노드보다 작거나 같은 값을 갖는 완전 이진 트리이며, 최대 힙은 반대입니다. 이러한 속성은 우선순위 큐에서 가장 높은 우선순위(또는 가장 낮은 값)를 가진 요소를 빠르게 찾을 수 있도록 합니다.

 

우선순위 큐 구현방법

그렇다면 이진 트리를 사용해 우선순위 큐를 구현하는 방법을 알아보겠습니다.

 

데이터 저장 시

 

데이터 삭제 시

 

위의 이미지처럼 우선순위 큐에 데이터를 저장 및 삭제할 경우 다른 자료구조에 비해 효율적으로 진행됩니다. 시간복잡도는 트리의 높이만큼 비교연산을 진행하기 때문에 O(log2​n)이 나옵니다.