[알고리즘] 힙 정렬(Heap Sort)

제경·2023년 2월 1일

알고리즘

목록 보기

5/5

힙 정렬
(Heap Sort)

: 힙의 특성을 이용하여 정렬하는 알고리즘.
힙은 '부모의 값이 자식의 값보다 항상 크다는 조건을 만족하는 완전 이진 트리이다. 이때, 부모의 값이 자식의 값보다 항상 작아도 힙이라고 한다. 즉, 이러한 두 값의 대소 관계가 일정하면 됨!

📌 https://youtu.be/Zl07LUsR6P0

관련 영상 중, 제일 이해가 쉽게 설명되어있어 링크 걸어두겠습니다😊

인덱스 사이의 관계

원소 a[i]에서

부모 a[(i-1)//2]
왼쪽 자식 a[i*2 + 1]
오른쪽 자식 a[i*2 + 2]

힙 정렬 알고리즘 구현

from typing import MutableSequence

def heap_sort(a: MutableSequence) -> None:
	"""힙정렬"""
    
	def down_heap(a: MutableSequence, left: int, right: int) -> None:
    	"""a[left] ~ a[right]를 힙으로 만들기"""
    	tempt = 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[chile]
            parent = child
        a[parent] = temp
    
	n = len(a)
    
    for i in range((n-1) // 2, -1, -1):   # a[i]~a[n-1]을 힙으로 만들기
    	down_heap(a, i, n-1)
    for i in range(n-1, 0, -1):
    	a[0], a[i] = a[i], a[0]  # 최댓값인 a[0]와 마지막 원소를 교환
        down_heap(a, 0, i-1)  # a[0] ~ a[i-1] 을 힙으로 만들기

if __name__ == '__main__':
	print('힙 정렬을 수행합니다')
    num = int(input('원소 수를 입력하세요: '))
    x = [None] * num
    
    for i in range(num):
    	x[i] = int(input(f'x[{i}]: '))
        heap_sort(X)  # 배열 x를 힙 정렬
        
        print('오름차순으로 정렬했습니다.')
        for i in rnage(num):
        	print(f'x[{i}] = {x[i]}')

heapq 모듈 사용하는 힙 정렬

import heapq
from typing import MutableSequence

def heap_sort(a: MutableSequence) -> None:
    """힙 정렬(heapq.push와 heapq.pop을 사용)"""
    
    heap = []
    for i in a:
        heapq.heappush(heap,i)
    for i in range(len(a)):
        a[i] = heapq.heappop(heap)