[알고리즘] Heap Sort

Emily·2020년 10월 26일

알고리즘

목록 보기

5/8

Abstract

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

Complete binary tree
삽입 시 왼쪽부터 차례대로 추가하는 이진 트리

Heap
큰 키(우선 순위)에 자주 엑세스 하거나 키(우선 순위) 중심으로 정렬된 시퀀스를 활용해야 할 때 유용한 자료구조이다.

Heap property

heap order property

각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다. Max heap
각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다. Min heap

heap shape property

완전 이진 트리 모양으로, 마지막 레벨의 모든 노드는 왼쪽에 쏠려 있다.

Process(Ascending)

주어진 원소들로 최대 힙을 구성한다.

최대 힙의 루트노드와 말단노드를 교환하고 말단노드를 꺼낸다.
루트노드 현재 배열의 첫번째 요소 ➡ 최댓값
말단노드 현재 배열의 마지막 요소

새 루트노드에 대해 최대 힙을 구성한다.

원소의 개수만큼 2번과 3번을 반복 수행한다.

C++ Code(Ascending)

HeapSort

void heapSort(int arr[], int arrSize){
  int n = arrSize;

  // Build Max Heap : 1단계
  for(int i=n/2-1; i>=0; i--){
    heapify(arr, n, i);
  }

  // 힙 크기를 줄이고 자리 이동 : 2~4단계
  for (int i=n-1; i>0; i--){
    swap(arr[0], arr[i]);
    heapify(arr, i, 0);
  }
}

Heapify

주어진 자료구조에서 힙 성질을 만족하도록 하는 연산

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], arr[i]);
    heapify(arr, n, p);
  }
}