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

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

1. Heap Sort를 배우기 전에

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

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

▶ Tree 자료구조

https://devraphy.tistory.com/45

▶ Heap 자료구조

https://devraphy.tistory.com/54

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 자료구조의 시간복잡도

from http://devraphy.tistory.com/385 by ccl(A) rewrite - 2021-09-09 01:26:50