heapSort
-
[Sort] 힙 정렬(Heap Sort]CSE/Sort 2015. 6. 12. 15:52
힙 정렬(Heap Sort) 정의: 힙이라는 자료구조를 이용하여 정렬하는 방법 힙은 삭제 연산을 수행하면 가장 최상위 루트원소를 반환한다. 최상위 루트원소는 힙 내부에서 가장 큰 원소이다. 힙정렬.... 힙을 이용해서 정렬을 하므로 굉장히 쉽게 사용되죠~ 왜냐면 힙 구현해 놓고 삭제 연산을 하면 정렬이 되니깐요!!! 한번 봅시다 ! 1단계 자 이렇게 최대 힙이 구성이 되어있습니다!!! 여기서 힙의 삭제연산을 합니다!! 삭제 연산은 루트 를 반환한다고 했죠??? 루트를 반환하고 힙은 다시 최대 힙을 구성합니다! 아래처럼 말이죠~ 1단계 끝!! 2단계 삭제 연산을 진행해야 겠죠??? 아래처럼 진행됩니다!! 계속 힙안에 있는 원소를 삭제 시키는 겁니다... 3단계 계속 삭제... 힙이 보잘것 없어서 아예 없어..