[자료구조] 파이썬 heapq 라이브러리는 어떻게 구현될까?

파이썬 라이브러리는 어떻게 구현할까?

무조건 작은 숫자가 0번 인덱스, 1번이 트리의 루트는 고정이다.

그리고 부모가 인덱스 k일 때 2k의 값은 2k+1보다 크다는 공식을 통해 구현된다

 

+ 23.11.14

왜 트리의 루트를 0번 인덱스부터 시작하지 않을까?

루트를 1에서 시작하면 부모 노드를 찾을 때 단순히 i // 2만 해주면 되는 반면

루트를 0에서 시작하면 (i-1) // 2를 해야하는 번거로움이 있다.

삽입 연산은 → heappush

가장 마지막 인덱스에 값을 넣고 (현재 인덱스) // 2로 부모 인덱스를 찾아서 비교한다

이때 비교의 기준이 작은 것이 올라가면 최소힙, 큰 것이 올라가면 최대힙이 된다.

삭제 연산은 → heappop

파이썬 같은 경우 이미 하나를 빼서 0번 인덱스에 넣어놓는다

0번이 빠지면 1번 인덱스를 0번에 넣고

1번 인덱스가 빠진 자리에 마지막 인덱스 숫자를 넣어서 자식노드들과 비교해서 위치시킨다

부모 인덱스에 곱하기 2를 하면 왼쪽 자식 인덱스를 찾을 수 있다 그리고 계속 비교해서 힙사이즈를 넘어가면 종료

 

이러한 원리에 의해 파이썬 힙의 0번째 인덱스는 최소값이지만 1번, 2번에 다음으로 작은 원소가 있다라고는 보장할 수 없는 것이다

 

힙(heap) 이란 ?

힙(heap) 이란 ?