8. Array(배열) - Heap Sort(1)

1. Heap Sort를 배우기 전에

- Heap Sort라는 이름에서 알 수 있듯이, Heap 자료구조를 이용해 배열을 정렬하는 알고리즘이다. 

- Heap Sort를 이해하기 위해서는 2가지 개념을 우선적으로 알아야한다.

 

▶ Tree 자료구조 

https://devraphy.tistory.com/45

Data Structure - 트리(Tree) & 이진탐색트리(Binary Search Tree)

 

▶ Heap 자료구조

https://devraphy.tistory.com/54

Data Structure - Heap(1)

---

2. Heap에 대하여

- Heap은 Priority Queue와 함께 자주 사용되는 자료구조다. 

- 즉, 데이터가 쌓이는 순서대로 출력되는 것이 아니라 어떤 규칙에 의해 출력되는 자료구조다.

   ex) 큰 수 부터 차례대로 출력된다, 작은 수 부터 차례대로 출력된다. 

 

- Heap은 완전이진트리의 구조가진 자료구조로 다음과 같은 특성을 가진다. 

  ▶ 항상 트리의 왼쪽부터 채워진다. 

  ▶ 부모노드 > 자식노드 

 

- Heap은 Max Heap과 Min Heap으로 구분된다. 

  ▶ Max Heap은 루트노드가 항상 최대값이다. 

  ▶ Min Heap은 루트노드가 항상 최소값이다.

 

https://www.geeksforgeeks.org/heap-data-structure/

 

a) Heap에 대한 이해 

- 다음 예시를 함께 보면서 Heap이 어떻게 동작하는지 알아보자. 

- 위의 배열을 Max Heap으로 만들면 다음과 같은 구조를 이룬다. 

 

- Max Heap의 루트노드는 항상 최대값이므로, 최대값을 검색하는데 걸리는 시간복잡도는 O(1)이다. 

 

- 여기서 11이라는 새로운 수를 추가하면 어떻게 정렬이 이루어질까? 

 

 

b) pop()

- pop은 heap의 루트노드를 출력하는 함수다.

- max heap은 최대값을, min heap은 최소값을 계속해서 출력한다. 

- pop을 통해 루트노드가 출력되고나면, 재정렬하는데 O(log n)의 시간복잡도가 걸린다. 

- 왜 그런지 재정렬 과정을 알아보자. 

 

 

c) Heap을 Array로 표현하는 방법

- 지금까지 Heap을 완전이진트리 구조로 그려가며 알아보았다.

- 하지만, 개발자는 Heap을 코드로 구현해야 된다. 그러므로 Heap을 배열로 구현한다.

- 어떻게 Heap을 배열로 구현하는지 알아보자.

 

d) Heap에 새로운 수가 추가될 때, 배열로 표현하는 방법

 

e) Heap 자료구조의 시간복잡도