[자료구조] Heap(힙)



Heap(힙) 이란?

한마디 버전:

(한글) 데이터에서 최대값과 최소값을 빠르게 찾기위해 고안된 완전 이진트리 형태의 자료구조. 

(영문) The data Structure of Complete Binary Tree to find efficiently Maximum or Minimum values.



1. 기본 구조

  • 힙은 2가지의 구조를 가질 수 있습니다.
  • Max Heap (최대힙) : 각 부모노드는 자식노드들 보다 항상 거나 최소한 같다.
  • Min Heap (최소힙) : 각 부모노드는 자식노드들 보다 항상 작거나 최소한 같다.

아래는 최대힙 구조입니다.




2. 이진탐색트리와 힙은 어떻게 다른가?

공통점 :

  • 모두 이진트리 구조를 사용함

차이점:

  • 힙 구조는 각 자식 노드들 보다 부모노드의 크기가 크거나 같고, 또는 작거나 같습니다.
  • 그리고 자식노드 둘 중 어느것이든 클 수 있습니다. 기준이 없음(반정렬상태)
  • 이진탐색트리는 부모노드가 자식노드들 보다 항상 크거나 작을 필요가 없습니다.
  • 이진탐색트리의 자식노드는 부모노드보다 크면 오른쪽으로 작으면 왼쪽으로 배치된다.

 이진탐색트리는 탐색을 위한 구조이고, 힙은 최소값, 최대값을 찾는 구조입니다.



3. 어떻게 사용하나요?

삽입 :

  • 기본적으로 왼쪽 최 하단부 부터 채워집니다.(왼쪽부터 채워진 완전한 트리의 형태: 완전 이진트리)

삭제 : 

  • 힙의 경우 루트노드에서 삭제하는 경우 밖에 없습니다. 자식노드를 삭제할 일은 없어요. (최대값, 최소값만을 찾기위함)
  • 가장 최근에 삽입된 데이터를 루트노드로 올리고 해당 자식노드들 보다 작으면 스왑해 나가는 식으로 힙 구조를 유지한다.

변경 :

  • 우선 채웁니다. 그리고 부모노드보다 크면 해당 노드와 그 노드의 부모노드가 스왑됩니다. 이 방법으로 최상단 노드까지 진행하여 스왑합니다. (Max Heap, Min Heap일 경우 반대)



4. 왜 힙을 사용해야 하나요?

데이터를 큐나, 배열에 데이터를 넣고 최대값이나 최소값을 찾으려면 최악의 경우 일일히 하나씩 데이터를 검사해야 하기때문에 O(n)의 시간복잡도를 가집니다. 하지만, 힙을 사용하면 O(log n)으로 시간복잡도가 현격하게 줄어듭니다.



5. 힙의 단점?

  • Heap은 느슨한 정렬상태(반정렬상태) 입니다. 완벽히 정렬되지 않고 가장 큰 수나 가장 작은 수만을 찾기 위함입니다.
  • 배열등을 Heap구조로 바꾸는데 역시 시간이 듭니다. Heapify() 라는 함수가 파이썬에게는 있습니다.



6. 키포인트

  • MAX 또는 MIN 값을 구하기 위한 자료구조입니다.
  • 시간복잡도는 O(log N) 입니다.
  • 완전이진트리구조 입니다.



7. 파이썬으로 Heap 구현하기

파이썬에는 heapq라는 라이브러리가 있습니다. 그것을 사용해서 구현할 수 있습니다.

import heapq as hq

data = [21, 67, 33, 13, 40, 89, 71, 19]
# 바로 heapify 해도 되지만 따로 리스트를 만들어 진행합니다.
heap_data = list()
hq.heapify(heap_data)

for d in data:
# heappush를 이용하여 데이터를 넣습니다.
hq.heappush(heap_data, d)

print('>>> 최소힙 큰수 3:', hq.nlargest(3, heap_data))
print('>>> 최소힙 최소값 제거:', hq.heappop(heap_data))
print('>>> 제거 후 데이터:', heap_data)


# 맥스 힙 구현
data = [21, 67, 33, 13, 40, 89, 71, 19]
# Heapq 라이브러리에서 따로 맥스힙 구현이 힘들어 데이터를 음수화 합니다.
data = [-x for x in data]
heap_data = list()
hq.heapify(heap_data)

for d in data:
hq.heappush(heap_data, d)

print('>>> 최대힙 가장 작은수 3:', hq.nlargest(3, heap_data))
# 음수로 반환되니 -1을 곱합니다.
print('>>> 최대힙 최대값 제거:', hq.heappop(heap_data)* -1)
print('>>> 제거 후 데이터:', heap_data)


data = [21, 67, 33, 13, 40, 89, 71, 19]
print('>>> 파이썬 Built-in Min함수:', min(data))
print('>>> 파이썬 Built-in Max함수:', max(data)) >>> 최소힙 큰수 3개: [89, 71, 67] >>> 최소힙 최소값 제거: 13 >>> 제거 후 데이터: [19, 21, 33, 67, 40, 89, 71] >>> 최대힙 가장 작은수 3개: [-13, -19, -21] >>> 최대힙 최대값 제거: 89 >>> 제거 후 데이터: [-71, -40, -67, -19, -21, -33, -13] >>> 파이썬 Built-in Min함수: 13 >>> 파이썬 Built-in Max함수: 89
  • [[a.original_name]] ([[a.file_size | fileSizer]])
좋아요[[ postLike | likePlus ]]
공유
라이언

“Lead Python Engineer”

댓글 [[totalCommentCount]]
[[ comment.author__nick_name ]] [[ comment.datetime_updated | formatDate]] (수정됨)

[블라인드 처리된 글 입니다.]

답장
[[ sub.author__nick_name ]] [[ sub.datetime_created | formatDate ]] (수정됨)

취소
댓글을 남겨주세요.
'컴퓨터공학' 관련 최신 포스트
[[ post.title ]]
[[ post.datetime_published_from | DateOnly ]]