📌 힙 정렬의 동작 방식

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

📌 최소 힙 구조로 만들기

🎈 1회차 삽입:

원소 7을 삽입합니다

🎈 2회차 삽입:

3을 삽입하는데, 7보다 작으므로 3과 7을 변경합니다

🎈 3회차 삽입:

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

🎈 4회차 삽입:

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

🎈 5회차 삽입:

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

🎈 6회차 삽입:

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

🎈 7회차 삽입:

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

🎈 8회차 삽입:

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

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

📌 힙 정렬

최소힙에서 내림차순 정렬된 배열을 얻기 위해선 아래와 같은 방법을 사용합니다

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

🛠️ 내림차순 배열 생성 과정 (최소힙 사용)

초기 최소힙 구조의 배열은 다음과 같습니다 [1, 3, 2, 6, 8, 5, 4, 7]
이제 내림차순 배열을 생성하겠습니다
추출된 원소는 기존 배열의 마지막에 배치됩니다

🎈 1회차 heapify:

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

🎈 2회차 heapify:

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

🎈 3회차 heapify:

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

🎈 4회차 heapify:

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

🎈 5회차 heapify:

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

🎈 6회차 heapify:

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

🎈 7회차 heapify:

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

🎈 8회차 heapify:

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

내림차순 정렬된 배열이 완성되었습니다

🚀 최종 정렬 결과

최종적으로 기존 배열은 아래와 같은 내림차순 형태가 됩니다
[8, 7, 6, 5, 4, 3, 2, 1]

✍️ 결론

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