heap

2 posts

[파이썬] TypeError: < not supported

파이썬에서 힙(heap)이나 우선순위 큐(PriorityQueue)를 사용하다 보면 다음과 같은 에러를 만날 수 있습니다. 이번 포스팅에서는 위 에러를 해결하는 방법에 대해서 알아보록 하겠습니다. 객체 정렬 기준 힙과 우선순위 내부적으로 이진 트리를 이용해서 데이터를 정렫된 상태로 유지하고 있습니다. 그런데 이 정렬이라는 게 가능하려면 원소 간의 대소 비교가 가능해야합니다. 예를 들어, 숫자나 문자와 같은 기본형 데이터는 대소 비교가 간단합니다. 1보다 2가 크고, a보다 b가 크다는 것은 일반적으로 알려진 사실이기 때문에 자료구조

파이썬의 heapq 모듈로 힙 자료구조 사용하기

데이터를 정렬된 상태로 저장하기 위해서 사용하는 파이썬의 heapq(힙큐) 내장 모듈에 대해서 알아보겠습니다. 힙 자료구조 heapq 모듈은 이진 트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공합니다. 자바에 익숙하신 분이라면 PriorityQueue 클래스를 생각하시면 이해가 쉬우실 것 같습니다. min heap을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치합니다. 내부적으로 min heap 내의 모든 원