Heap Sort

 

---

Heap Sort

---

 

 

 

0. 개요

 

앞서 다뤘던 내용들은 자료구조를 사용하지 않는 알고리즘이었다. (Insertion Sort, Merge Sort 등)

그러나 자료구조를 사용할 경우 더 효율적으로 문제를 풀 수 있는 경우가 생기며, 대표적으로 Max heap를 사용하는 Heap Sort가 있다.

 

 

1. 자료구조 heap

 

자료구조 heap, 특히 max heap에 대해서 알아봅시다.

Max Heap이 되기 위해서는 다음 조건을 만족해야한다.

 

1) a complete binary tree여야함

- tree 구조에서 마지막 level을 빼고는 모두 차 있어야 함

- 마지막 level은 왼쪽부터 오른쪽으로 차있음

 

2) Max-heap Property를 가지고 있어야 함

- key(x) >= keys(at x's children)

- 부모 노드의 값이 가장 커야 

 

2. Heap Sort

 

Heap Sort는 위에서 다룬 Heap의 성질을 활용하여 정렬하는 것이다. 주요 알고리즘은 다음과 같다.

따라서 Heapsort를 이해하기 위해서는 `BUILD-MAX-HEAP` 함수와 `MAX-HEAPIFY` 함수에 대해서 이해해야 한다. 각 내용은 다음과 같다.

 

2.1 MAX-HEAPIFY

 

Max-Heapify 기본 아이디어: 자료구조 전체를 heap으로 만들기 위함임

• 왼쪽 자식 트리와 오른쪽 자식 트리가 모두 heap property를 만족하지만, root만이 조건을 만족하지 않는 경우

 

 

전반적인 과정

• 두 자식노드 중 더 큰 값을 선택
• 부모 노드보다 자식 노드의 더 큰 값이 큰지 확인
• 자식 노드의 값이 더 크면 바꿈
  • 만약 바꾸는 경우, 바꾼 노드가 다시 heap property를 만족하는지 확인

출처: https://ict-nroo.tistory.com/55

 

 

Psuedocode

각각 subtree의 부모 노드를 불러오고, 이를 각각 기존 부모 노드와 비교한다.

이론에서는 두 자식 노드 중 큰 것과 비교한다고 하는데, 그렇게 진행하지는 않는다.

 

Time Complexity - O(lgn)

 

 

2.2 BUILD-MAX-HEAP

 

 

 

 

2.3 Time Complexity of Heap Sort

O(n)번 진행하고, 각 MAX-HEAPIFY마다 O(lgn)이므로 결과는 O(n*lgn)

 

 

 

3. Heap Sort Time Complexity - 심화

 

기본적으로 Heap Sort의 Time Complexity는 O(n*lgn)이다. 그러나 증명을 통해 O(n)임을 증명할 수도 있다. 증명 과정은 아래와 같다.

 

 

 

 

 

참고

https://ict-nroo.tistory.com/55