힙 정렬 Heap Sort

Intro::

힙정렬에 대해 알아보자.

정의

완전 이진 트리를 기본으로 하는 힙(Heap) 자료구조를 기반으로한 정렬 방식이다.

1. 최대 힙을 구성

2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임

3. 힙의 사이즈가 1보다 크면 위 과정 반복

시간복잡도

O(n log n)

코드

package algorithm;

import java.util.*;

public class HeapSort {
	public static void main(String[] args) {
		int[] arr = { 230, 10, 60, 550, 40, 220, 20 };

		heapSort(arr);
		System.out.println(Arrays.toString(arr));
	}

	public static void heapify(int arr[], int n, int i) {
		int p = i;
		int l = i * 2 + 1;
		int r = i * 2 + 2;

		if (l < n && arr[p] < arr[l]) {
			p = l;
		}

		if (r < n && arr[p] < arr[r]) {
			p = r;
		}

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

	public static void heapSort(int[] arr) {
		int n = arr.length;

		for (int i = n / 2 - 1; i >= 0; i--) {// 부모 노드들에 대해서
			heapify(arr, n, i);
		}
		// 현재 루트 노드가 가장 큰 수
		for (int i = n - 1; i > 0; i--) {
			swap(arr, 0, i);
			heapify(arr, i, 0);
		}
	}

	public static void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}

References::