9. Array(배열) - Heap Sort(2)

0. 시작하기 전에

- 이전 포스팅에서 Heap 자료구조에 대해 간단하게 알아보았다.

- 이제 Heap을 이용해 어떻게 정렬을 하는지 알아보자. 

---

1. Heap 구현

a) 파이썬에서 Heap을 구현하는 방법 

- 파이썬에서 Heap을 구현려면 2가지만 배우면 된다. 

  ▶ heapq 라이브러리

  ▶ heapify 함수 

import heapq

case = [9, 7, 5, 3, 1]
heapq.heapify(case)
print(case) #[1,3,5,9,7] 반환

 

b) heapq 라이브러리는 Min Heap만 만들 수 있다. 

- heapify 함수를 이용하면 Min Heap을 만들 수 있다.

- 하지만, heapq 라이브러리에는 Max Heap을 만들어 주는 함수는 따로 존재하지 않는다. 

- 그러므로 약간의 노하우가 필요하다. (아래에서 다룰 예정입니다.)

 

---

2. Heap Sort 란?

- Heap 정렬은 정렬되지 않은 배열(array)을 Heap으로 바꾸어 정렬하는 알고리즘이다. 

- 굳이 배열을 Heap으로 바꾸어 정렬하는 이유는, 더 적은 시간복잡도를 가지기 때문이다. 

- 즉, 완전이진트리를 사용하므로 검색에 있어서 더욱 빠르다. 

 

a) Heap Sort의 정렬과정 

- Heap 정렬은 정렬되지 않은 배열을 오름차순 또는 내림차순으로 정렬할 때 사용하는 알고리즘이다.

- 내림차순으로 정렬할 때에는 Min Heap을 사용하면 되지만, 

- 오름차순으로 정렬할 때에는 Max Heap을 사용해야 한다. 

- 그러므로 어떤 배열을 Heap Sort를 이용하여 오름차순으로 정렬해보자. 

 

 

b) Heap Sort의 시간복잡도

 

 

c) Heap Sort의 안정성

 

---

3. Heap Sort 코드구현

from typing import List
import heapq

# 최대 힙을 이용해 오름차순으로 정렬하라. 
def heap_sort(case:List[int]) -> List[int]:

  # min Heap을 max Heap으로 만드는 과정 
  case = [-1 * n for n in case] # 1) 배열의 모든 요소에 -1을 곱한다
  heapq.heapify(case) # 2) min Heap을 만든다. 

  sorted = [0] * len(case) # [0, 0, 0, 0, 0, 0]

  for i in range(len(case) - 1, -1, -1):
  # 위에서 모든 요소에 -1을 곱한 이유는 이 과정을 위해서다. 
  # min Heap에서 가장 큰 수를 제일 먼저 뽑기 위해서는 음수로 변환시킨 것이다. 
  
    #이 과정이 이해가 안간다면 아래의 스크린 샷을 참고하기를 바란다. 
    largest = -1 * heapq.heappop(case) 
    sorted[i] = largest

  return sorted

print(heap_sort(case = [3, 5, 7, 9, 4, 2]))

정렬 결과

 

a) for문 이해하기 

- for문 이전에, 왜 배열의 모든 요소를 음수로 만드는지 (모든 요소에 -1을 곱한 부분)

- for문 내부에서는 어떤 일이 벌어지는지의 이해가 가지 않는다면 다음 사진을 참고하자. 

정렬 결과

---

4. Min Heap을 Max Heap으로 만드는 방법 

# 4) Min Heap으로 Max Heap 만들기 
import heapq

nums = [4, 1, 7, 3, 8, 5]
heap = []
max_heap = []

for num in nums:
  heapq.heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  max_heap.append((heapq.heappop(heap)[1]))  # index 1

print(max_heap)

출력 결과

---

[참고자료]

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법