3.1 Sorting - 3.1.4 Heap Sort

CS - 3. Common Algorithms - 3.1. Sorting - 3.1.4 Heap Sort

 

💡Heap sort is a comparison based sorting algorithm. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

힙 정렬은 비교 기반 정렬 알고리즘입니다. 먼저 최대 요소를 찾은 다음 최대 요소를 마지막에 배치하는 선택 정렬과 유사합니다. 나머지 요소에 대해서도 동일한 과정을 반복합니다.

 

앞에서 데이터의 양이 많거나 무작위로 배열된 데이터일 경우 퀵, 힙 같은 고급 정렬 알고리즘을 사용하는 것이 좋다고 말하였습니다.

그래서 얼마나 좋은지 알아봅시다.

 

힙 정렬 (Heap Sort)은 힙이라는 특별한 이진 트리 자료구조를 사용하는 정렬 알고리즘 입니다.

힙은 https://parkpakrsu.tistory.com/331

Data structures (with python) - 3. Heap

다뤘습니다.

 

한줄로 요약한다면

'최댓값 또는 최솟값을 빠르게 찾기 위해 사용되는 부모-자식 노드간의 관계를 바탕으로 정렬되는 완전 이진 트리.'

라고 할수 있겠다.

부모 노드의 값이 자식노드의 값보다 항상 크거나 작은특성을 가지고 있다.

이런 특성 때문에 힙은 큐나 정렬을 하는데 강력한 성능을 발휘한다.

 

힙 정렬(Heap Sort)는 이러한 힙의 특성을 이용합니다.

먼저 배열을 최대 힙의 형태로 변환한 뒤, 힙으 ㅣ루트에 항상 최대값이 위치하게끔 만듭니다.

그리고 이 최대값을 힙의 마지막 노드와 교환하고 힙 크기를 하나 줄여 정렬을 진행합니다.

 

힙 정렬의 동작 과정은 이렇습니다.

1. 입력 배열을 최대 힙으로 변환합니다.

2. 힙의 루트(최대값)을 힙의 마지막 요소와 교환합니다.

3. 힙 크기를 1 줄입니다.(즉, 마지막 요소를 힙에서 제거합니다.)

4. 새로운 루트에 대해 힙을 재조정합니다.

5. 위의 과정을 힙의 크기가 1이 될 떄까지 반복합니다.

 

 

In Python

import heapq

def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

파이썬에서는 heapq 모듈을 통해 구현할수 있습니다.

 

좀더 구체적인 예시를 들겠습니다.

# 1. 힙생성
import heapq
numbers = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(numbers)

# 2. 원소 추가 :heappush O(log n)
heapq.heappush(numbers, -5)

# 3. 원소 제거 :heappop O(log n)
smallest = heapq.heappop(numbers)

# 4. 최대/최소값 조회 : 파이썬의 힙은 최소 힙(min heap)이므로, 가장 작은 값은 항상 인덱스 0, 즉 힙의 루트에 위치합니다.
# 따라서 O(1)의 시간 복잡도로 최소값을 조회할 수 있습니다.
smallest = numbers[0]

# 5. 우선순위 큐 수현 : 튜플의 리스트를 힙으로 만들면 첫 번쨰 원소를 기준으로 최소 힙이 구성됩니다.
# 이를 이용하면 우선순위와 값이 쌍으로 이루어진 데이터를 관리하는데 유용합니다.
priority_queue = []
heapq.heappush(priority_queue, (2, 'code'))
heapq.heappush(priority_queue, (1, 'eat'))
heapq.heappush(priority_queue, (3, 'sleep'))
while priority_queue:
    print(heapq.heappop(priority_queue)[1])  # 'eat', 'code', 'sleep' 순서로 출력

 

 

정리

 

힙 정렬의 시간 복잡도는 O(log n)으로, 대부분의 경우에서 효율적으로 작동합니다.

힙 정렬은 데이터의 입력 상태에 관계없이 일정한 실행 시간을 가지는 것이 특징입니다.

즉, 이미 정렬된 데이터나 역순으로 정렬된 데이터에ㅔ 대해서도 시간 복잡도는 변하지 않습니다.

따라서, 정렬되지 않은 데이터를 정렬해야 하는 경우나 최악의 경우의 시간 복잡도가 중요한 경우 유용하게 사용할 수 있습니다.