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

Question

heappush를 사용하면 리스트인 a가 heap의 형태로 바뀌게 되는건지 궁금합니다! 교수님 풀이와는 다르게 heappush를 사용하지 않고 리스트에 append 하는 형식으로 값을 추가한 후에 heappop을 사용하게 되면 최솟값이 나오지않는것같습니다.

김태원 · Answer

안녕하세요^^ 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가 그 자리에 넣어줍니다.