[Data Structure] Heap

1. Heap의 개념

   • 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조
   • 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조
   • 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지함
     • 큰 값이 상위 레벨이 있고, 작은 값이 하위 레벨에 있다는 정도
     • 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리를 말함
   • 힙 트리에서는 중복된 값을 허용함 ↔ 이진 탐색 트리에서는 중복된 값을 허용하지 않음

2. Heap의 종류

   

   • 최대 힙 (Max Heap)
     • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
     • key(부모 노드) ≥ key(자식 노드)
   • 최소 힙(Min Heap)
     • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
     • key(부모 노드) ≤ key(자식 노드)

3. Python Heap

   • import heapq를 이용하여 heap 라이브러리 import
   • heapq.heappush(‘리스트’, item) : 리스트에 item 추가
   • heapq.heappop(‘리스트’) : heap에서 가장 작은 원소 pop → 비어있으면 IndexError
   • heapq.heapify(‘리스트’) : 리스트를 즉각적으로 heap으로 변환
   • heapq.nlargest(n, ‘리스트’) : 큰 값부터 n개를 리스트 형태로 출력
   • heapq.nsmallest(n, ‘리스트’) : 작은 값부터 n개를 리스트 형태로 출력

➰ References

https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html