힙 정렬은 기본적으로 힙 자료구조를 기반으로 한다. 간단히 힙 자료구조에 대해 알아보면 힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'이다. 최솟값 or 최댓값을 빠르게 찾아내는 것이 힙의 핵심이다. 위 사진은 heap tree를 시각화한 것이다. 하지만 트리의 인덱싱을 아는 사람이라면 위 사진이 무엇인가 이상해 보일 거다. 바로 형제 노드 간의 정렬은 되어있지 않다는 점이다. 이를 weak heap, 반정렬 상태 등등이라 부른다. "아니 그러면 어떻게 정렬을 하나요?" 위에서 힙의 핵심은 최솟값 or 최대값을 빠르게 찾아내는 것이라 했다. 힙의 root node는 항상 우선순위가 1등이다. 즉 최소값 또는 최댓값이란 것이다. 이를 이용해 root node를 삭제..
