📌 힙 정렬의 동작 방식

실제 예시를 통해 힙 정렬의 동작 방식을 살펴보겠습니다
[7, 3, 5, 2, 8, 1, 4, 6]배열을 힙 정렬 알고리즘을 통해 오름차순 정렬하겠습니다

📌 최대 힙 구조로 만들기

🎈 1회차 삽입:

원소 7을 삽입합니다

🎈 2회차 삽입:

3을 삽입하는데, 7이 여전히 크므로 순서를 그대로 유지합니다

🎈 3회차 삽입:

5를 삽입합니다. 위와같이 정렬됩니다

🎈 4회차 삽입:

2을 삽입합니다 위와같이 정렬됩니다

🎈 5회차 삽입:

8을 삽입합니다 위와같이 정렬됩니다

🎈 6회차 삽입:

1을 삽입합니다 위와같이 정렬됩니다

🎈 7회차 삽입:

4를 삽입합니다 위와같이 정렬됩니다

🎈 8회차 삽입:

6을 삽입합니다 위와같이 정렬됩니다

최종적으로 [8, 7, 5, 6, 3, 1, 4, 2] 형태로 최대 힙 배열 구조가 됩니다

📌 힙 정렬

최대 힙에서 오름차순 정렬된 배열을 얻기 위해서는 아래와 같은 방법을 사용합니다

최대 힙의 루트를 꺼내 새로운 배열에 삽입하고, 남은 힙을 다시 최대 힙으로 재구성합니다
이 과정을 heapify라고 하며, 힙이 완전히 비워질 때까지 반복합니다

🛠️ 오름차순 배열 생성 과정 (최대힙 사용)

초기 최대힙 구조의 배열은 다음과 같습니다 [8, 7, 5, 6, 3, 1, 4, 2]
이제 오름차순 배열을 생성하겠습니다

🎈 1회차 heapify:

루트(8)를 꺼내고, 마지막 원소 2을 루트로 이동 후 heapify합니다

→ 추출값: `[8]`  
남은 힙: `[7, 6, 5, 2, 3, 1, 4]`

🎈 2회차 heapify:

루트(7)를 꺼내고, 마지막 원소 4을 루트로 이동 후 heapify합니다

→ 추출값: `[7, 8]`  
남은 힙: `[6, 4, 5, 2, 3, 1]`

🎈 3회차 heapify:

루트(6)을 꺼내고, 마지막 원소 1를 루트로 이동 후 heapify합니다
→ 추출값: [6, 7, 8]
남은 힙: [5, 4, 1, 2, 3]

🎈 4회차 heapify:

루트(5)를 꺼내고, 마지막 원소 3을 루트로 이동 후 heapify합니다
→ 추출값: [5, 6, 7, 8]
남은 힙: [4, 3, 1, 2]

🎈 5회차 heapify:

루트(4)를 꺼내고, 마지막 원소 2를 루트로 이동 후 heapify합니다
→ 추출값: [4, 5, 6, 7, 8]
남은 힙: [3, 2, 1]

🎈 6회차 heapify:

루트(3)을 꺼내고, 마지막 원소 1을 루트로 이동 후 heapify합니다
→ 추출값: [3, 4, 5, 6, 7, 8]
남은 힙: [2, 1]

🎈 7회차 heapify:

루트(2)을 꺼내고, 마지막 원소 1을 루트로 이동 후 heapify합니다
→ 추출값: [2, 3, 4, 5, 6, 7, 8]
남은 힙: [1]

🎈 8회차 heapify:

마지막 원소(1)을 꺼내면 힙이 비워집니다
→ 추출값: [1, 2, 3, 4, 5, 6, 7, 8]

원본 최대 힙 구조의 배열이 비워지고,
새롭게 오름차순 정렬된 배열이 완성되었습니다

🚀 최종 정렬 결과

최종적으로 얻어진 배열은 아래와 같은 오름차순 형태가 됩니다.
[1, 2, 3, 4, 5, 6, 7, 8]

✍️ 결론

힙 정렬 알고리즘으로 배열을 오름차순 정렬 하려면 다음 순서대로 동작합니다
1. 먼저 기존 배열을 최대 힙 구조로 변경합니다
2. 힙의 원소를 추출해, 기존 배열의 마지막에 재배치하고 기존 힙은 heapify합니다
3. 최종적으로 기존 배열의 값은 오름차순 형태가 됩니다