우선순위 큐
를 위하여 만들어진 자료구조*최대 힙 트리
나 최소 힙 트리
를 구성해 정렬을 하는 방법*최대 힙
을 구성하고 오름차순 정렬을 위해서는 최소 힙
을 구성하면 된다.정렬해야 할 n개의 요소들로 최대 힙(완전 이진 트리 형태)을 만든다.
→ 주어진 트리, 즉 배열을 뒤에서 부터 부모보다 자식이 더 큰 경우 변경(반복) → 최대 힙
그 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.
가장 큰 값과 변경
한다. (모든 노드 수행)재귀
<aside> 💡
힙 트리(이진 트리)에서 부모와 자식간의 값 변경 방법
부모 노드의 인덱스
= 자식 노드 인덱스 / 2
왼쪽 자식 노드의 인덱스
= 부모 노드 인덱스 * 2
오른쪽 자식 노드의 인덱스
= 부모 노드 인덱스 * 2 + 1
</aside>
<aside>
💡 주로 우선순위 큐
와 BFS(while, if-else)
를 묶은 형태의 알고리즘으로 작성하면 된다.
</aside>
ref: https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html