백준 문제를 풀다가 heap를 사용하는 문제가 있어 heap에 대해 정리하고자 한다.

heap

정의

우선순위 큐를 구현하기 위해 사용되는 자료구조 중 하나로, 특정 순서를 유지하는 완전 이진 트리다.

우선순위 큐

우선순위의 개념을 큐에 도입한 자료구조

kind of heap(힙의 종류)

max heap(최대 힙)

부모 노드의 키 값이 자식 노트의 키 값보다 크거나 같은 완전 이진 트리

min heap(최소 힙)

부모 노드의 키 값이 자식 노드의 키 값 보다 작거나 같은 완전 이진 트리

heap in Python(파이썬에서의 힙)

heap 내장 모듈

import heapq

heapq 모듈을 import 하여 heap를 쉽게 사용할 수 있다.
heapq 모듈은 min heap를 사용한다

heap 함수 종류

힙 생성

heap = []

list와 같이 생성해 주면 된다.

원소 추가

heapq.heappush(heap, 10)

heaqp.heappush 키워드를 사용하고 인자로
heaqp.heappush(푸시할 힙, 값)

힙 자료형으로 변환

arr = [10,20,30]
heapq.heapify(arr)

이미 생성된 리스트가 있을 경우
heapq.heapify(리스트명) 을 통해 리스트 자료형을 힙 자료형으로 바꿀수 있다.

원소 삭제

a = heapq.heappop(heap)

heappop 함수는 가장 작은 원소를 힙에서 제거함과 동시에 그를 결과값으로 리턴한다

인덱스 접근

heap도 list와 동일하게 인덱스 접근이 가능하다.