[자료구조] heap 이란?

개념

• 힙(Heap)이란 최댓값과 최솟값을 빠르게 찾기 위해 고안된 자료구조이다. O(logn)의 시간 복잡도를 가진다.
• 삽입 연산, 삭제 연산이 가능하다.

특징

• 리스트에 새로운 값을 집어넣거나 빼낼 때 (push, pop) 리스트의 값들이 오름차순으로 자동 정렬한다.
• 정렬 비용을 감소시켜 코드의 효율성을 높일 수 있다.

코드

1) heappush() : 리스트에 새로운 값을 삽입
2) heappop() : 리스트의 최솟값을 빼냄

import heapq
heap = []

# 1) heap 리스트에 새로운 값 num을 삽입
heapq.heappush(heap, num)

# 2) heap 리스트의 가장 작은 값을 빼냄
heapq.heappop(heap)

참고

• 힙 큐 알고리즘 - 공식문서
• https://hocheon.tistory.com/70