[알고리즘] 힙 정렬(Heap Sort)

힙 정렬(HeapSort)

힙이란?

http://devheat.tistory.com/12 참고

설명

힙의 최상위 노드에는 가장 큰 값이 존재한다는 특성을 이용해 정렬하는 알고리즘
최대 힙 혹은 최소 힙의 노드 삭제를 연속으로 수행해 값이 가장 큰 노드부터 내림차순 혹은 오름차순으로 꺼낼 수 있다.

구현

구현은 이전 포스팅 http://devheat.tistory.com/12 에서 만든 delete 메소드를 연달아 호출하면 된다.
최상위 노드를 꺼내고, 최하위 노드를 최상위에 위치시켜 다시 하향 heapify를 수행하는 것이 핵심

소스코드

번외

이전 포스트와 마찬가지로 Generic Heap에도 정렬 기능을 추가할 수 있다.

구현 힙 사용 예제 (Comparable을 구현한 String 클래스를 사용)