힙이라고 하는 특별한 자료 구조를 사용하여 정렬을 한다. 그것은 전이진 트리를 이용하게 되는 것인데 이를 이용함으로 임의의 노드는 언제나 자식 노드들보다 큰 값을 가지게 된다. 즉, 트리 전체에서 루트가 언제가 가장 큰 값이 되는 것이다.
힙 정렬은 이러한 힙을 사용하여 정렬을 한다. 가장 큰 값을 갖게 되는 루트 값을 출력(삭제)시킨 후에 다시 나머지 노드들로 힙을 구성하게 되고, 이러한 과정을 계속하여 반복해 나간다면 가장 큰 값으로부터 내림차순으로 정렬이 된다.
분야
hwp
