[컴][알고리즘] heap sort - 힙소트

목차

1. Insertion sort
2. quick sort
3. merge sort
4. heap sort

개념

min heap 또는 max heap 을 이용한다.
이 두개의 힙은 complete binary tree 의 모양을 갖는다.
Max heap 이나 min heap 을 만들 수 있으면 힙정렬을 사용할 수 있다.

핵심은 heapify

정렬되지 않은 리스트를 일단 맥스힙(max heap)으로 만들자.
쭉 훑으며 내려가면서(traverse, 트래버싱)
가장 큰 값이 위로 올라오도록 한다.

맥스힙인 상태에서 기장 위의 값을 가장 뒤의 값과 바꾸고
나머지 녀석을 다시 맥스힙으로 만든다.
이때 처음부터 훑으면서 내려간다.

그러면서 큰 녀석과 스왑하고 그 다음 내려가서 또 두개의.차일드 중에서 큰.녀석과 스왑하고 해서 결국 스왑할 곳이 없는 상태에서 멈춘다.
그리고 다시 맥스값을 마지막녀석과 바꾼다.

min heap 인 경우
민힙(min heap)도 처음에 훑으면서 맨위 값을 차일드와 비교해서 차일드가 작으면 스왑하고 만약 둘다 작으면 더 작은 값과 스왑하고 쭉 내려간다.
근데 스왑한 녀석이랑 그 부모와 비교해서 스왑당한 녀석이 더 작으면 그녀석을 위로 올린다.



http://proneer.tistory.com/m/293
heap 정렬을 잘 설명해 준다.
동영상(?) 도 있어서 이해하기 쉽다.
heap 은 complete binary tree 이다. 는 전제를 알고 있어야 한다. 이 전제를 바탕으로 만들어 놓은 sort 이다.

heap sort

• heap sort 에 걸리는 time complexity : O(nlogn)
• n : n 개의 node
• logn : binary tree 의 depth,
  min heap 을 만들려고 하는데, node 가 가장 작은 값이 가장 밑에 있는 경우 heapify 를 하는 데에 logn 번의 비교를 하고 올라와야 한다.

heap 정렬은 n/2 로부터 시작하는데
그런데 index 가 0 으로부터 시작하지 않고, 1로 부터 시작하는 경우
n/2 는 마지막 leaf node 의 부모node 가 된다.

1. 즉 마지막 node 의 부모 node를 선택(이제 부터 1개씩 줄어들면, 자식node 를 가진 부모node 들을 역순으로 순차적으로 접근할 수 있다.)
   부모node 와 자식node 의 값을 비교해서
2. min heap
   부모node 가 작으면 놔두고,
   부모node 가 크면 자식node 와 swap
   swap 이 돼서 내려갔는데, 그 node의 child node와 비교했는데, 여전히 크다면 다시 swap 한다.(즉, 조건을 만족하는 상태에서 가능한한 가장 밑으로 내려 보낸다.)
3. min heap 이 되어 있는 상태에서는 root 에 가장 작은 값이 있다.
4. 이제 root 를 가장 마지막 leaf node 와 swap 하자.
   그러면 가장 작은 값이 가장 밑으로 내려가게 된다.
5. 이제 가장 작은 값을 제외한 나머지 부분을 다시 min heap 으로 만든다.

See Also

1. [질문] 퀵 정렬과 힙 정렬의 비교에 관해 질문드립니다., 2009년 11월, KLDP