힙 정렬
힙은 부모의 값이 자식의 값보다 항상 크다라는 조건을 만족하는 완전 이진 트리입니다. 대소 관계가 일정하다고 볼 수 있습니다. (부모의 값 ≥ 자식의 값)
파이썬에서 힙 정렬은 heap모듈 함수를 통해 쉽게 구현가능합니다. 파이썬의 힙 정렬 함수는 다음과 같습니다.
- heappush(heap, data): 힙에 새로운 데이터를 삽입한다.
- heappop(heap): 힙에서 루트 노드(최소값)를 꺼낸 후 삭제한다.
- heapify(x): 주어진 배열을 힙 구조로 변환한다.
→ 원래 힙정렬이 기본은 최솟값 정렬이다. 그러므로 최댓값을 구할때에는 -을 사용하여 최댓값 정렬로 바꾸어서 풀고 나중에 -를 다시 붙여 원래값으로 되돌려야한다.
힙의 루트는 최댓값일때, 힙 정렬을 완료하는 과정을 보여드리겠습니다.
https://yermi.tistory.com/entry/알고리즘-힙-정렬Heap-Sort-힙-트리를-활용한-정렬-알고리즘
이러한 과정을 통해 힙 정렬을 완료하면, 부모와 자식 원소들은 다음과 같은 관계가 성립합니다.
부모: a[(i-1) // 2]
왼쪽 자식: a[i * 2 + 1]
오른쪽 자식: a[i * 2 + 2]
그러면 최댓값인 루트를 삭제한 경우는 어떻게 될까요?
루트가 제거되면 맨마지막 원소가 루트로 이동합니다. 그후 큰값을 가진 자식과 위치를 교환하며 힙을 재정렬합니다.(자식의 값이 본인보다 작거나 리프 위치에 도달하면 종료) 다음은 루트 44가 제거됐을때 재정렬한 과정을 보여줍니다.
https://velog.io/@hyeonahhh/힙-정렬-Heap-Sort
++ 힙 정렬의 시간 복잡도는 어떻게 될까요?
단순 선택정렬에서는 최댓값인 원소를 선택하는 시간 복잡도는 O(n)으로 총 시간 복잡도는 O(n^2)이지만,
힙정렬에서 다시힙으로 만드는 작업의 시간 복잡도는 O(logn)으로 총 O(nlogn)입니다.
(힙정렬은 루트를 알맞은 위치까지 내리는 작업이 스캔할 때마다 선택 범위가 절반으로 줄어드는 이진 탐색과 비슷)