자료구조 - 힙 정렬

힙 정렬이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법이다.

내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다.

예를 들어 {2, 8, 5, 3, 9, 1} 배열은 다음과 같은 힙 정렬의 과정으로 오름차순 정렬할 수 있다.

 

2 8 5 3 9 1 배열을 이진 트리로 구현

 

 

 

배열 순대로 생성된 트리를 max heap 으로 만든다.

 

 

 

 

루트 노드를 마지막 노드와 위치를 바꾼다.

 

 

 

그렇게 9는 마지막 인덱스에 고정된다.

 

 

 

루트 노드에 위치한 1은 다시 트리를 max heap 으로 만들기 위해 heapify 과정을 거친다.

 

 

 

다시 루트 노드에 있는 8은 마지막 노드인 2와 위치를 바꾼다.

 

 

그렇게 8은 마지막 인덱스-1 에 고정된다.

 

 

루트 노드에 위치한 2는 max heap 을 유지하기 위해 heapify 과정을 거친다.

 

 

 

루트 노드인 5와 마지막 노드인 1의 위치를 바꾼다.

 

 

 

5는 마지막 인덱스-2에 고정된다.

 

 

 

다시 max heap 을 유지하기 위해 heapify 과정을 거친다.

 

 

 

루트 노드인 3과 마지막 노드인 2의 위치를 바꾼다.

 

 

 

 

교환 후 3은 마지막 인덱스-3에 고정된다.

 

 

 

max heap 을 유지하기 위해 heapify 과정을 거친다.

 

 

 

루트 노드인 2와 마지막 노드인 1의 위치를 바꾼다.

 

 

 

2는 마지막 인덱스 -4에 고정되고 나머지 1도 마지막 인덱스 -5에 고정되어 정렬이 완료된다.

 

 

▼ 힙 정렬 코드

import java.io.*;
import java.util.*;

public class Main {
    public static void HeapSort(int arr[], int n) {
        heapify(arr, n);

        for (int i = n - 1; i > 0; i--) {
            swap(arr, 0, i);
            heapify(arr, i);
        }
    }

    public static void heapify(int arr[], int n) {
        int p = (n - 1) / 2;

        for (int i = p; i >= 0; i--) {
            int leftChild = i * 2 + 1;
            int rightChild = i * 2 + 2;
            int maxIndex = i;

            if (leftChild < n && arr[leftChild] > arr[maxIndex]) {
                maxIndex = leftChild;
            }

            if (rightChild < n && arr[rightChild] > arr[maxIndex]) {
                maxIndex = rightChild;
            }

            if (maxIndex != i) {
                swap(arr, i, maxIndex);
                heapify(arr, n);
            }
        }
    }

    public static void swap(int arr[], int first, int last) {
        int temp = arr[first];
        arr[first] = arr[last];
        arr[last] = temp;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("정렬할 요소의 개수 : ");
        int N = sc.nextInt();

        int arr[] = new int[N];
        System.out.print("요소 입력 : ");
        for (int i = 0; i < N; i++)
            arr[i] = sc.nextInt();

        HeapSort(arr, N);

        System.out.print("정렬된 배열: ");
        for (int i = 0; i < N; i++)
            System.out.print(arr[i] + " ");
    }
}

 

 

실행 결과