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

안녕하세요^^

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가 그 자리에 넣어줍니다.