정렬 - 힙 정렬

힙 정렬 (Heap Sort)

최대/최소 힙을 이용한 정렬 방법으로 내림차순 정렬을 하려면 최대 힙을, 오름차순 정렬을 하려면 최소 힙을 이용한 정렬입니다.

그렇다면 힙(Heap)은 무엇일까요?

힙의 개념

힙(Heap)을 영어사전에서 찾아보면 "더미"라고 되어 있습니다.

컴퓨터 분야에서의 힙은 완전이진트리 기반의 "더미"와 모습이 비슷한 자료구조를 말합니다.

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조 입니다.

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말합니다.

- Key(A) >= Key(B)

- 힙은 중복된 값을 허용합니다.

최대 힙 : Key(부모노드) >= Key(자식노드)

최소 힙 : Key(부모노드) <= Key(자식노드)

힙의 구현

힙은 완전 이진트리이기 때문에 각각의 노드에 차례대로 번호를 붙일 수 있습니다.

이 번호를 배열의 인덱스로 생각하면 배열에 힙의 노드들을 저장할 수 있습니다.

- 힙을 저장하는 표준적인 자료구조는 배열

- 프로그램 구현을 쉽게 하기 위해 배열 0번은 사용하지 않습니다.

어떤 노드의 왼쪽이나 오른쪽 자식의 인덱스를 알고 싶다면 아래와 같은 식을 이용하면 됩니다.

- 왼쪽 자식의 인덱스 : (부모의 인덱스) * 2

- 오른쪽 자식의 인덱스 : (부모의 인덱스) * 2 + 1

부모의 인덱스를 알고 싶다면 아래와 같은 식을 이용하면 됩니다.

- 부모의 인덱스 : (자식의 인덱스) / 2

힙 정렬의 특징

힙 정렬은 전체적으로 O(nlog 2n)의 시간이 걸립니다. 이러한 시간 복잡도는 삽입 정렬 같은 간단한 정렬 알고리즘이 O(n^2)걸리는 것에 비하면 좋은 편입니다.

힙 정렬이 가장 유용하게 사용 될 때는 바로 모든 데이터를 정렬하는 것이 아니라 가장 큰 값 몇개만 필요할 때 입니다.

- 힙의 앞부분만 사용하면 되기 때문

힙 정렬의 구현

정렬해야할 n개의 요소들을 최대 힙으로 저장한 후에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장하면 정렬이 완료됩니다.