[Algorithm] 힙 정렬

안전 정렬 : 동일한 값에 기존 순서가 유지 (버블, 삽입, 병합)

 

불안정 정렬 : 동일한 값에 기존 순서가 유지X (선택, 퀵, 힙)

 

📌힙 정렬 

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

 

불안정 정렬(unstable sort)에 속하며 평균, 최선, 최악 시간 복잡도 모두 O(n log n)임. 가장 크거나 작은 값을 구할 때 유용 

 

완전 이진 트리(complete binary tree)?
이진 트리의 한 종류로서 왼쪽 부터 차례대로 노드를 삽입하는 트리(왼쪽부터 채움, 왼쪽이 비어있는데 오른쪽이 채워져있을 수 없음)

 

시간복잡도

log₂n(완전 이진 트리)

 

과정

1. 최대 힙을 구성
2. 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임
3. 힙의 사이즈가 1보다 크면 위 과정 반복

 

https://en.wikipedia.org/wiki/Heapsort

https://commons.wikimedia.org/wiki/File:Heap_sort_example.gif

 

 

import java.util.Arrays;

public class HeapSort {

    public static void heapsort(int[] array) {
        int n = array.length;

        for (int i = n / 2 - 1; i >= 0; i--) {
        	// 최초 heap 구성
            heapify(array, n, i);
        }

        // 최대 원소를 맨 끝에 정렬하고 다시 heap구성하는 과정
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }

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

        //  array[p] < array[l] 오름차순, array[p] > array[l] 내림차순
        
        //왼쪽 자식노드
        if (l < n && array[p] > array[l]) {
            p = l;
        }
        //오른쪽 자식노드
        if (r < n && array[p] > array[r]) {
            p = r;
        }

        //부모노드 < 자식노드
        if(i != p) {
            swap(array, p, i);
            heapify(array, n, p);
        }
    }

    public static void swap(int[] array, int p, int i) {
        int temp = array[p];
        array[p] = array[i];
        array[i] = temp;
    }

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

        System.out.println(Arrays.toString(array));
    }
}

 

 

 

1번째 heapify

일반 배열을 힙으로 구성하는 역할

자식노드로부터 부모노드 비교

• n/2-1부터 0까지 인덱스가 도는 이유는?
• 부모 노드의 인덱스를 기준으로 왼쪽 자식노드 (i2 + 1), 오른쪽 자식 노드(i2 + 2)이기 때문

2번째 heapify

요소가 하나 제거된 이후에 다시 최대 힙을 구성하기 위함

루트를 기준으로 진행(extract 연산 처리를 위해)

 

 

언제 사용하나요?

 

다시 최대 힙을 구성할 때까지 부모 노드와 자식 노드를 swap하며 재귀 진행

퀵정렬과 합병정렬의 성능이 좋기 때문에 힙 정렬의 사용빈도가 높지는 않음.

하지만 힙 자료구조가 많이 활용되고 있으며, 이때 함께 따라오는 개념이 힙 소트

힙 소트가 유용할 때

• 가장 크거나 가장 작은 값을 구할 때
• 최소 힙 or 최대 힙의 루트 값이기 때문에 한번의 힙 구성을 통해 구하는 것이 가능
• 최대 k 만큼 떨어진 요소들을 정렬할 때
• 삽입정렬보다 더욱 개선된 결과를 얻어낼 수 있음

 

 

참조사이트 : github.com/gyoogle/tech-interview-for-developer/blob/master/Algorithm/HeapSort.md

참조사이트 : gaemi606.tistory.com/entry/%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-sort?category=785070