Algorithm | Sort : 힙 정렬

힙 정렬(Heap Sort) ?

 힙 정렬은 말 그대로 자료구조 중 하나인 힙을 이용하여 정렬을 하는 방법이다. 내림차순 정렬을 위해서는 최대힙을, 오름차순 정렬을 위해서는 최소힙을 구성하면 된다. 힙에 대한 설명은 아래의 포스팅을 참고하자.

 

Algorithm | 자료구조 : 힙(Heap)

 

 힙의 삭제 연산은 최상위 노드를 삭제한 후 최하위 노드를 최상위로 끌어와 다시 힙의 구조를 만족시키는 방향으로 재정렬 한다. 그러므로 힙의 삭제연산을 이용하여 최상위에 위치한 루트 노드(최소 힙일 경우 최소값, 최대 힙일 경우 최대값)의 값을 꺼내와 차례대로 배열에 다시 저장해주면 값들이 정렬된다.

 

 힙 정렬의 시간복잡도는 힙 트리의 전체 높이가 log2n(완전 이진 트리)이므로 하나의 요소를 힙에 삽입하거나 삭제할 때 힙을 재정비 하는 시간이 O(log2n)의 시간이 걸린다. 여기에 요소의 개수가 n개 이므로 전체적으로는  O(nlog2n)의 시간 복잡도를 가지게 된다.

힙 정렬 구현(in JAVA)

import java.util.ArrayList;

public class HeapSort {
  private ArrayList<Integer> heap;

  
  public HeapSort() {
    heap = new ArrayList<>();
    heap.add(0);  // 인덱스를 1부터 사용하기 위해서
  }

  private void swap(int i1, int i2) {
    int temp = heap.get(i1);
    heap.set(i1, heap.get(i2));
    heap.set(i2, temp);
  }
  
  private void insert(int val) {
    heap.add(val);
    int p = heap.size() - 1;
    
    // 최상위 노드에 도달하거나 부모가 자식보다 작을 때까지 반복문 진행
    while(p > 1 && heap.get(p/2) > heap.get(p)) {
      swap(p/2, p);
      p = p / 2;
    }
  }
  
  private int delete() {
    int deletedValue = heap.get(1);
    heap.set(1, heap.get(heap.size() - 1)); // 최상위 노드의 값을 최하위 노드의 값으로 변경
    heap.remove(heap.size() - 1); // 최하위 노드 삭제
    int p = 1;

    while(p * 2 < heap.size()) {
      int min_child = p*2;
      // 자식 노드들 중 더 작은 놈이랑 교환할거임
      if(p*2+1 < heap.size() && heap.get(p*2) > heap.get(p*2+1)) {
        min_child = p*2 + 1;
      }

      // 부모 노드가 더 큰값일 경우 최소힙에 만족하지 못하므로 교환
      if(heap.get(p) > heap.get(min_child)) {
        swap(p, min_child);
        p = min_child;
      }else { // 최소힙을 만족시켰으면 반복문 탈출
        break;
      }
    }
    return deletedValue;
  }

  public void heapSort(int[] arr) {
    for (int num : arr) {
      insert(num);  // 배열을 힙에 저장
    }

    for (int i = 0; i < arr.length; i++) {
      arr[i] = delete();  // 힙의 최상위 값을 꺼내서 배열 재설정
    }
  }
}

 

 최소 힙을 이용하여 오름차순 정렬을 구현하였다. 

---

Reference

 

· 힙 정렬이란? - https://gmlwjd9405.github.io/2018/05/10/algorithm-heap-sort.html