Heap에 관한 설명은 간략히 하고 heapq내장모듈을 사용하는 방법을 작성해보겠다.
Heap이란
heapq는 Min Heap 자료구조를 제공한다.
우선순위큐 Heap을 생각하면 된다. Heap의 주요 개념을 간략히 살펴보면 다음과 같다.
Heap자체는 우선순위큐를 구현하기 위한 자료구조이다.
우선순위 큐란?
이전의 큐는 FIFO로써 먼저 들어온 값이 먼저 나가는 구조의 자료형이였다. 그런데 우선순위 큐는 우선순위가 높은 값이 먼저 나갈 수 있도록 구현한 것이다.
이를 구현하는데는 이진트리가 아닌 다른 방법도 있으며, 이진트리로 구현한 것이 바로 Heap이다.
그렇다면, Min Heap과 Max Heap이 어떤 것일지는 예상이 간다. Min Heap은 더 작은 값에게 우선순위를 준다는 것이고 Max Heap은 더 큰 값에게 우선순위를 준다는 것이다.
Heap의 insert와 remove
내가 학교에서 배운 Heap의 insert와 remove의 설명이 와닿아서 그 설명을 상기해서 설명해 보겠다.
먼저, Insert는 다음과 같이 설명한다.
"회사의 신입 사원이 점점 승진해서 자신의 능력에 맞게 올라가는 형태" → 이를 upheap이라고 한다.
remove는 다음과 같이 설명한다.
"말단직원이 사장의 자리를 차지한후 점점 강등당하는 것"→이를 downheap이라고 한다.
위와 같은 알고리즘을 이용해서 Heap 정렬을 구현할 수 있다.
heapq 모듈은 리스트를 힙처럼 다룰 수 있도록 도와준다. 리스트를 힙처럼 다룰 수 있도록 하기 때문에, 리스트와 별개의 자료구조가 아니다.
heapq모듈
push
위에서 말했듯이 파이썬에서 heap은 리스트와 다르지 않다.
C언어에서도 Heap을 구현할때 배열을 이용한다.
따라서 첫번째 인자로 heap으로 만들 리스트를 넣고 두번째로 입력할 값을 넣어준다.
pop
heap을 heappop에 넣어줌으로써 높은 우선순위를 가지는 값을 pop해준다.
최소값 peek하기
최소값을 살펴보기만 하기 위해서는 리스트와 다를바가 없기 떄문에 0번인덱스의 값을 살펴보면 된다.
두번째 인자에 tuple이 들어가는 경우
만약 두번째 인자에 튜플이 들어가는 경우 튜플의 첫번쨰 인자를 우선적인 비교대상으로 삼고 비교하고 만약 같을 경우 두번째, 세번째 인자를 비교해서 우선순위를 따진다.
하지만 보이는 바와 같이 저장되는 값은 튜플이 저장되게 돼있다.
