[java] 파이썬에서 힙 정렬 구현하기

15 Dec 2023

java

힙 정렬(Heap Sort)은 배열을 정렬하는 효율적인 알고리즘 중 하나입니다. 이 알고리즘은 일반적으로 “힙” 자료구조를 사용하여 정렬을 수행합니다.

힙(Hep) 자료구조

힙은 완전 이진 트리로 구현되는 자료구조로, 각 노드의 값이 해당 노드의 자식 노드의 값보다 작거나 큰 특성을 가지고 있습니다. 이는 최소 힙과 최대 힙 두 가지 유형이 있습니다.

이미 구현된 힙 자료구조를 사용하여 힙 정렬 알고리즘을 구현할 수 있습니다.

파이썬에서 힙 정렬 알고리즘 구현

다음은 파이썬에서의 힙 정렬 알고리즘의 예제 코드입니다.

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    
    if l < n and arr[i] < arr[l]:
        largest = l
        
    if r < n and arr[largest] < arr[r]:
        largest = r
        
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heapSort(arr):
    n = len(arr)
    
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    for i in range(n-1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

# 예제 배열
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("정렬된 배열:")
print(arr)

위의 코드는 주어진 배열을 정렬하는 데 사용될 수 있는 힙 정렬 알고리즘의 구현 예제입니다.

결론

힙 정렬은 효율적인 정렬 알고리즘이지만, 일반적으로 퀵 정렬이나 병합 정렬과 같은 다른 알고리즘보다는 느린 경향이 있습니다. 그러나 이해하기 쉽고 구현하기 간단하며, 추가적인 메모리를 요구하지 않는 장점을 가지고 있습니다.

참고 자료

GeeksforGeeks - Heap Sort