[5.27] 06-8 힙 정렬

[힙 정렬heap sort 알아보기] -> 선택 정렬 응용

heap

- 부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 부분 이진 트리

* 부분 : 형재의 대소 관계가 정해져 있지 않다

트리

- 노드node가 연결된 계층 구조

- root (젤 윗값) / parent node > child node = sibling node / leaf (가장 말단 노드)

- 완전 이진 상태 : 완전 - 부모는 왼쪽 자식부터 추가하여 모양을 유지한다. 

- 이진 : 자식은 최대 2개

[힙 정렬의 특징]

힙에서 최댓값은 루트에 위치한다 (부모 >= 자식이므로)

알고리즘

step 1. 최댓값인 루트를 꺼낸다

step 2. 루트가 사라진 나머지 부분을 다시 힙으로 만든다. -> 반복

[루트를 삭제한 힙의 재구성]

[힙 정렬 알고리즘 알아보기]

step1. 배열을 힙으로 만들기

step2. i = n-1로 두고, a[0]과 a[i]을 교환

step3. a[0] ~ a[i-1]를 힙 구조로 만들기

step4. i -= 1한 뒤 반복

[배열을 힙으로 만들기]

bottom-up으로 전체 배열을 합으로 만든다. 

#힙 정렬 알고리즘 구현하기

from typing import MutableSequence

def heap_sort(a:MutableSequence) -> None:
  def down_heap(a:MutableSequence, left:int, right:int) -> None:
    temp = a[left]

    parent = left
    while parent < (right + 1) // 2:
      cl = parent * 2 + 1
      cr = cl + 1
      child = cr if cr <= right and a[cr] > a[cl] else cl
      if temp >= a[child]:
        break
      a[parent] = a[child]
      parent = child
    a[parent] = temp
  n = len(a)

  for i in range((n-1) // 2, -1, -1):
    down_heap(a, i, n-1)
  for i in range(n-1, 0, -1):
    a[0], a[i] = a[i], a[0]
    down_heap(a, 0, i-1)
  
a = [5, 6, 7, 9, 10, 1, 2, 3, 4, 8]
heap_sort(a)
print(a)

힙 정렬의 시간 복잡도

O(nlogn)

heapq 모듈을 사용하는 힙 정렬

heappush() 함수

heappop() 함수