Prompt Title: 자바 힙 정렬 구현

힙 정렬(Heap Sort) 알고리즘의 의사 코드와 자세한 설명은 다음과 같습니다.

1. 최대 힙 구성 (Build Max Heap)
2. 정렬 수행 (Perform Sorting)

phpCopy code
function heapSort(arr):
    n = length(arr)

    // Build Max Heap
    for i from n/2 - 1 to 0 (inclusive) do:
        heapifyMax(arr, n, i)

    // Perform Sorting
    for i from n - 1 to 1 (inclusive) do:
        swap(arr[0], arr[i])
        heapifyMax(arr, i, 0)

여기서 사용되는 heapifyMax 함수의 의사 코드는 다음과 같습니다.

sqlCopy code
function heapifyMax(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2

    if left < n and arr[left] > arr[largest]:
        largest = left

    if right < n and arr[right] > arr[largest]:
        largest = right

    if largest != i:
        swap(arr[i], arr[largest])
        heapifyMax(arr, n, largest)

설명:

1. 최대 힙 구성 (Build Max Heap)

• 주어진 배열을 최대 힙(max-heap)으로 변환하는 과정입니다. 최대 힙은 부모 노드가 자식 노드보다 크거나 같은 값을 가지는 완전 이진 트리입니다.
• n/2 - 1부터 0까지 역순으로 heapifyMax 함수를 호출하여 하위 트리를 최대 힙 구조로 만듭니다.

2. 정렬 수행 (Perform Sorting)

• 배열의 마지막 원소부터 첫 번째 원소까지 역순으로 진행합니다.
• 배열의 첫 번째 원소(최대값)와 현재 원소(i)를 교환합니다.
• 교환 후, 배열의 크기를 i로 줄여서 다시 heapifyMax를 호출하여 최대 힙 구조를 유지하면서 정렬을 수행합니다.
• 이 과정을 반복하면 배열이 오름차순으로 정렬됩니다.

heapifyMax 함수는 주어진 인덱스를 기준으로 하위 트리를 최대 힙 구조로 만드는 과정입니다. 이를 위해 해당 인덱스와 왼쪽 자식, 오른쪽 자식 중 가장 큰 값을 찾아서 부모 노드와 교환합니다. 교환 후에도 하위 트리를 최대 힙 구조로 만들기 위해 heapifyMax를 재귀적으로 호출합니다.