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

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

 

1. 힙 자료구조 개념 설명

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

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

 

힙과 우선순위 큐를 이해하기 전에 큐 자료구조에 대해 이해를 하면 좋습니다.

큐에 대한 소개는 아래 링크 참고 바랍니다.

https://rightbellboy.tistory.com/343

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

 

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

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

 

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

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

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

 

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

그 특성에 따라 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. 힙 자료구조 구현 예시 코드

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