Heapsort

일단 대충 요약하자면 Heapsort는 O(nlogn)의 시간복잡도를 자랑한다. 근데 그전에 Heap이 뭔지는 설명해야 할거 아닌가?

Ref : https://www.geeksforgeeks.org/dsa/heap-sort/

 

Heap

데이터 구조인 Heap은 거의 CBT로 볼수있는 array object라고 할 수 있겠다. 위 사진에서 볼 수 있듯 어떤 노드의 요소는 배열의 어떤 요소에 대응될 수 있을 것이다. 대충 배열 이름을 A라고 해보면, 트리의 루트는 A[1]이 될 것이고 이런식으로 치면 아래와 같이 PARENT/LEFT/RIGHT NODE를 구할 수 있을 것이다.

 

Parent :  [ i/2 ]
Left     : 2i
Right   : 2i + 1
when i is 0>=.

 

그리고 Binary한 Heap에는 두가지 종류가 있는데, 하나는 max-heap이고 다른 하나는 min-heap이 되시겠다. max-heap은 부모 노드가 자식보다 크거나 같은 경우, min-heap은 부모 노드가 자식보다 작거나 같은 경우를 의미한다. (참고로 Heapsort에서는 max-heap을 사용하고, 왼쪽  자식 노드와 오른쪽 자식 노드 사이의 크기 비교는 딱히 안해도 된다.)

 

Priority Queue

Heapsort 알고리즘은 그래서 일단 max-heap을 만듬으로서 시작된다. 뭐 대충 만들었다고 치면 어떤 input에 대한 최대 값이 처음에 저장될 테니까, 이걸 배열의 뒤로 유배 보내서 오름차순으로 정렬 가능하다고 할 수 있을 것이다. 이게 다 Heapify 과정 덕분이다, 얼마나 참 쉬운 것인가?

 

Ref : https://formulafunction.wordpress.com/2017/07/18/heapsort/

쨋든 그래서 대단한 알고리즘이라고 할 수 있겠다. 근데 문제는 quicksort가 일반적으로는 얘를 줘 팬다는 점이다. 근데 그럼에도 불구하고 많이 사용하는데 - 이게 Priority Queue라는 친구 덕분이다. Queue는 FIFO 자료구조이지만, Priority Queue는 우선순위가 가장 높은 데이터가 먼저 튀어나가는 Queue라고 할 수 있겠다. 아 물론 리스트로도 이걸 구현할 수 있겠으나...

 

구현 방식	삽입 (Enqueue / Push)	최댓값/최솟값 삭제 (Dequeue / Pop)
정렬되지 않은 배열	O(1) (맨 뒤 추가)	O(N) (전체 탐색)
정렬된 배열	O(N)$(자리 찾고 시프트)	O(1) (맨 앞 또는 맨 뒤)
이진 힙 (Binary Heap)	O(\log N)	O(\log N)

와 같이 Heap은 시간 복잡도를 logN으로 쳐내게 해준다. 차피 쳐내면 포인터만 조정해서 위로 올리면 되지 않겠는가 Heap은.