힙 자료구조 개념 설명 및 예시 코드 (1 base) (C/C++)

(예시 코드 및 이미지는 추후 추가 예정)

 

1. 힙 자료구조 개념 설명

힙(Heap)은 우선 순위 큐(Priority Queue) 중 가장 대표적으로 사용되는 자료구조입니다.

실제 제가 준비 중인 알고리즘 구현 시험에서도 빈번하게 사용되고 있어서 첫 게시글 대상으로 선정되었습니다.

 

우선 힙과 우선 순위 큐 소개에 앞서서

가장 기본적인 자료구조인 큐(Queue)에 대한 소개를 간단히 하겠습니다.

 

큐는 데이터를 넣고 뺄 수 있는 상당히 단순한 형태의 자료구조로

First In First Out(FIFO)라는 중요한 특성을 가지고 있습니다.

FIFO는 은행 혹은 맛집 등에서 방문한 순서대로 입장하는 일반적인 대기열을 생각하면 쉽게 이해할 수 있습니다.

(간단한 Queue 이미지 추가)

 

큐는 1차원 배열과 2개의 포인터 값(front, rear)만으로 쉽게 구현해볼 수 있습니다.

대표적으로 구현하여 사용하게 되는 함수는 ① 데이터를 넣는 enque, ② 데이터를 빼는 deque 입니다.

(간단한 예시 코드 추가)

(큐 소개 페이지로 따로 작성하고 링크만 첨부하는 형태로 변경)

 

우선 순위 큐는 일반적인 큐와는 다르게 데이터를 뺄 때, 즉 deque시

자료 구조 내에서 우선 순위가 가장 높은 데이터가 나오게 됩니다.

 

이러한 형태로 우선 순위대로 데이터를 뽑을 수 있는 자료구조를 우선 순위 큐라고 하고,

우선 순위 큐를 이해하고 구현하는 데에 가장 편한 '힙'을 우선 순위 큐와 동의어처럼 사용하고 있습니다.

(힙과 우선 순위 큐에 대한 검증 필요)

 

통상 힙의 우선 순위는 데이터 값의 최소값 혹은 최대값으로 정하는데

그 특성에 따라 min heap, 혹은 max heap이라고 불리고 있습니다.

 

max heap은 큰 값이 높은 우선 순위를 갖는 형태이므로

pop을 할 경우 해당 heap 내에서 가장 큰 값이 나오게 됩니다.

(통상 heap에서의 deque를 pop, enque를 push라고 칭합니다)

 

heap은 이진 트리 구조 형태로 구현되므로 n개의 데이터에서 최대값을 찾는데

최악의 경우를 기준으로 O(n)이 아닌 O(logn)의 시간복잡도를 갖게 됩니다.

(또한 데이터를 넣을 때(push)도 O(logn)의 시간복잡도를 갖게 됩니다)

 

이러한 특성이 있기 때문에 데이터가 자주 들어오고 나가지만,

매번 그 중 가장 큰 값 or 가장 작은 값을 찾아야 하는 경우 힙 자료구조를 사용하게 됩니다.

만약 위 같은 상황에서 힙이 아닌 정렬을 사용하게 된다면 오히려 시간 비용이 훨씬 커집니다.

(정렬은 데이터를 빼거나 찾는 상황이 별로 없는 상황인 경우

자료구조의 맨 끝에 저장해두고 필요할 때 한 번 씩 정렬해서 사용하는 형태로 쓰면 유리합니다)

(lazy update에 대한 page 작성 및 링크)

 

 

2. 힙 자료구조 구현 방식

heap에 대한 개념 설명은 마치고 1차원 배열을 사용하여 구현하는 방법을 설명해보겠습니다.

(max heap으로 작성 예정)

 

 

3. 힙 자료구조 구현 예시 코드

(위 내용 토대로 작성 예정)