파이썬 힙 정렬

1. Python의 힙 정렬 알고리즘
2. Python에서 힙 정렬 알고리즘 구현

이 자습서에서는 Python에서 힙 정렬 알고리즘을 구현하는 방법을 보여줍니다.

Python의 힙 정렬 알고리즘

힙 정렬은 Python에서 배열과 목록을 정렬하기 위한 강력한 알고리즘입니다. 매우 빠르고 병합 정렬 및 빠른 정렬과 같은 추가 공간을 차지하지 않기 때문에 인기가 있습니다.

힙 정렬의 시간 복잡도는 O(n*log(n))입니다.

힙 정렬은 데이터의 중간 상태를 저장하기 위해 더 이상 데이터 구조를 만들지 않는 내부 알고리즘입니다. 대신 원래 배열을 변경합니다.

따라서 데이터가 매우 클 때 많은 공간을 절약할 수 있습니다.

이 알고리즘의 유일한 단점은 매우 불안정하다는 것입니다. 배열에 서로 다른 인덱스에 동일한 값을 가진 여러 요소가 있는 경우 정렬하는 동안 해당 위치가 변경됩니다.

힙 정렬 알고리즘은 최소 또는 최대 힙을 재귀적으로 생성하고, 루트 노드를 제거하고, 배열의 정렬되지 않은 첫 번째 인덱스에 배치하고, 마지막 힙 요소를 루트 노드로 변환하는 방식으로 작동합니다.

이 프로세스는 힙 내부에 단일 노드가 남을 때까지 재귀적으로 반복됩니다. 결국 마지막 힙 요소는 배열의 마지막 인덱스에 배치됩니다.

잠시 생각해 보면 이 프로세스는 가장 큰 값이나 가장 작은 값을 선택하여 정렬된 배열의 맨 위에 배치하는 선택 정렬 알고리즘과 비슷합니다.

Python에서 힙 정렬 알고리즘 구현

먼저 원래 배열, 배열 길이 및 부모 노드의 인덱스를 사용하는 build_heap() 함수를 구현하는 방법을 살펴보겠습니다. 여기서 배열을 보면 마지막 상위 노드의 인덱스는 배열 내부 (n//2 - 1)에 있습니다.

마찬가지로 특정 부모의 왼쪽 자식에 대한 인덱스는 2*parent_index + 1이고 오른쪽 자식에 대한 인덱스는 2*parent_index + 2입니다.

이 예에서는 최대 힙을 생성하려고 합니다. 즉, 모든 부모 노드는 자식 노드보다 커야 합니다.

이를 위해 마지막 부모 노드에서 시작하여 힙의 루트 노드까지 위쪽으로 이동합니다. 최소 힙을 생성하려면 모든 부모 노드가 자식 노드보다 작아야 합니다.

이 build_heap() 함수는 왼쪽 또는 오른쪽 자식이 현재 부모 노드보다 큰지 확인하고 가장 큰 노드를 부모 노드와 교환합니다.

이 함수는 힙의 모든 상위 노드에 대해 이전 프로세스를 점진적으로 반복하기를 원하기 때문에 자신을 재귀적으로 호출합니다.

다음 코드 스니펫은 Python에서 위에서 언급한 built_heap() 함수의 작동 구현을 보여줍니다.

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2

    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index

    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index

    if largest_index != parent_index:
        arr[parent_index], arr[largest_index] = arr[largest_index], arr[parent_index]

        build_heap(arr, length, largest_index)

이제 배열 내에서 최대값을 가져와 힙의 루트에 배치하는 함수가 있습니다. 정렬되지 않은 배열을 가져와 build_heap() 함수를 호출하고 힙에서 요소를 추출하는 함수가 필요합니다.

다음 코드 스니펫은 Python에서 heapSort() 함수의 구현을 보여줍니다.

def heapSort(arr):
    length = len(arr)

    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)

    for element_index in range(length - 1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

배열 내에서 각 상위 노드의 build_heap() 함수를 점진적으로 호출합니다. length//2-1을 시작 색인으로 지정하고 -1을 종료 색인으로 제공하고 있으며 단계는 -1입니다.

즉, 마지막 부모 노드에서 시작하여 루트 노드에 도달할 때까지 인덱스를 1씩 점진적으로 줄입니다.

두 번째 for 루프는 힙에서 요소를 추출합니다. 또한 마지막 인덱스에서 시작하여 배열의 첫 번째 인덱스에서 멈춥니다.

이 루프에서 배열의 첫 번째 요소와 마지막 요소를 교환하고 루트 인덱스로 0을 전달하여 새로 정렬된 배열에서 build_heap() 함수를 실행합니다.

이제 우리는 Python에서 힙 정렬을 구현하는 프로그램을 작성했습니다. 배열을 정렬하고 위에서 작성한 코드를 테스트할 시간입니다.

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

출력:

Sorted array : [1, 2, 3, 4, 5, 6]

보시다시피 배열이 완전히 정렬되었습니다. 이것은 우리 코드가 잘 작동한다는 것을 의미합니다.

내림차순으로 정렬하려면 위에서 구현한 최대 힙 대신 최소 힙을 만들 수 있습니다.

이 튜토리얼의 시작 부분에서 최소 힙이 무엇인지 이미 논의했기 때문에 이 기사에서는 최소 힙을 설명하지 않습니다.

우리 프로그램은 다음과 같은 방식으로 작동합니다. 다음 블록은 코드 실행의 각 단계에서 배열의 상태를 보여줍니다.

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

build_heap() 함수는 힙에 3개의 상위 노드만 있기 때문에 3번 실행됩니다.

그 후 요소 추출 단계에서는 첫 번째 요소를 가져와서 마지막 요소로 교체하고 build_heap() 함수를 다시 실행합니다. 이 프로세스는 길이 - 1에 대해 반복되고 배열이 정렬됩니다.