힙 정렬

힙 정렬부터는 갑자기 생각해야 할 것들이 많아 졌다.

힙 정렬은 말 그대로 자료구조의 힙을 이용한 정렬 방식이다.

우선 힙의 특징은

- 완전 이진트리 구조를 가진다.

- 노드 중에 최대값 or 최소값을 빠른시간 내에 찾기위해 만든 자료구조다.

힙 정렬은 힙에 정렬 대상을 모두 넣었다가 다시 하나하나 꺼내면서 정렬을 한다.

장점은 성능이 앞에서 배운 버블, 선택, 삽입 정렬에 비해 월등히 우수하고 추가 메모리가 필요하지 않다.

단점은 데이터 구조에 따라 다른 정렬에 비해 늦을 수 있다는 점이며, 안정성이 보장되지 않는다.

(안정성이 보장되지 않는다는게 정확이 무슨 뜻인지는 잘 모르겠다.)

힙 정렬 코딩시 알아두어야 할 점은

노드하나를 i라고 가정할 때

노드 i의 부모노드 인덱스 : i/2 (단, i>1)

노드 i의 왼쪽 자식노드 인덱스 : i x 2

노드 i의 오른쪽 자식노드 인덱스 : i*2+1 이라는 점이다.

아래 간단한 예제를 들어놓았다.