인프런 커뮤니티 질문&답변

북극곰님의 프로필 이미지

작성한 질문수

파이썬 알고리즘 문제풀이 입문(코딩테스트 대비)

10. 최소힙

heap 구조에 대한 질문입니다!

해결된 질문

23.05.27 11:20 작성

·

305

0

heappush를 사용하면 리스트인 a가 heap의 형태로 바뀌게 되는건지 궁금합니다!

교수님 풀이와는 다르게 heappush를 사용하지 않고 리스트에 append 하는 형식으로 값을 추가한 후에 heappop을 사용하게 되면 최솟값이 나오지않는것같습니다.

답변 1

1

김태원님의 프로필 이미지
김태원
지식공유자

2023. 05. 27. 15:28

안녕하세요^^

heappush(a, x)를 하면 a를 단순 리스트로 생각하지 않고 a라는 1차원 리스트가 이진트리 형식인 힙구조라고 생각합니다. 1차원 리스트를 힙구조로 생각하고 컨트롤 할 수 있습니다. 1번 인덱스 값의 왼쪽 자식 노드는 2번인덱스, 오른쪽 자식 노드는 3인덱스, 2번 인덱스 값의 왼쪽 자식 노드는 4번 인덱스, 오른쪽 자식 노드는 5번 인덱스 이런식으로 생각합니다. 즉 i번 인덱스 값의 왼쪽 자식은 i*2인덱스, 오른쪽 자식은 i*2+1 인덱스와 같이 계산합니다.

즉 heappush(a, x)는 a리스트를 이진트리 힙구조라 행각하고, 이진트리인 힙구조에서 x숫자가 위치할 인덱스 위치를 upheap 방식(현재 x노드와 x의 부모 노드를 비교해서 최소힙이 되기 위한 x값의 위치 계산)으로 찾아 x가 그 자리에 넣어줍니다.