Krafton Jungle/3. TIL
[WEEK01] 힙 소트
munsik22
2025. 3. 18. 13:52
힙 정렬
힙heap이란 정렬된 이진 트리ordered binary tree를 의미한다.
- 최대 힙 : 상위 노드(부모)의 값 > 하위 노드(자식)의 값
- 최소 힙 : 상위 노드(부모)의 값 < 하위 노드(자식)의 값
- build-max-heap : 정렬되지 않은 배열에서 최대 힙을 만들어 낸다.
- heapify : build-max-heap과 비슷하지만, 배열의 일부분이 정렬된 상태라고 가정한다.
위와 같이 정렬을 하도록 지정된 배열에 대해 다음 단계를 수행한다.
- Max heap 만들기
- 가장 큰 item 제거하기
- item을 정렬된 부분배열에 넣기
def left(i):
return 2*i
def right(i):
return 2*i + 1
def parent(i):
return i//2
def max_heapify(a, heap_size, i):
l = left(i)
r = right(i)
largest = i
if l < heap_size and a[l] > a[i]:
largest = l
if r < heap_size and a[r] > a[largest]:
largest = r
if largest != i:
# swap elements
a[i], a[largest] = a[largest], a[i]
max_heapify(a, heap_size, largest)
def build_max_heap(a):
heap_size = len(a)
for i in range(heap_size//2, 0, -1):
max_heapify(a, heap_size, i)
def heap_sort(a):
build_max_heap(a)
for i in range(len(a)-1, 1, -1):
# swap elements
a[i], a[1] = a[1], a[i]
# after the swap the last element is now sorted, but the new root may break the max-heap condition
# fix it by calling max-heapify with a smaller heap size (sorted elements are out of the picture)
max_heapify(a, i, 1)
def main():
a = [None, 99, 0, 5, 20, 123, 0, -1, 72, 21, 22, 13, 8, 7, 67, 29, 1, 2, 4]
heap_sort(a)
print(a[1:])
a = [None, 3, 9, 2, 1]
heap_sort(a)
print(a[1:])
main()[출처] 4분 만에 힙 정렬
heapify
def heafity(arr, left, right):
tmp = arr[left]
parent = left
while parent < (right+1) // 2:
cl = parent * 2 + 1
cr = parent * 2 + 2
child = cr if cr <= right and arr[cr] > arr[cl] else cl
if tmp >= arr[child]: break
arr[parent] = arr[child]
parent = child
arr[parent] = tmp🔍 코드 분석
- arr: 힙을 구성할 배열
- left: 힙을 조정할 루트 노드 인덱스
- right: 힙의 마지막 인덱스 (배열 크기가 n이라면 right = n - 1)
1. 현재 루트 노드를 임시 변수로 저장
- tmp: 루트 노드의 값을 저장 (나중에 적절한 위치에 다시 배치)
- parent: 현재 부모 노드의 인덱스 (초기값은 left)
2. 왼쪽 자식이 존재하는 동안 반복
- (right+1) // 2는 마지막 내부 노드의 개수를 나타냄
(즉, 부모 노드가 존재할 수 있는 최대 위치) - parent < (right+1) // 2이면 현재 부모 노드가 리프 노드가 아님, 따라서 반복
3. 왼쪽과 오른쪽 자식 인덱스 계산
- cl: 왼쪽 자식의 인덱스
- cr: 오른쪽 자식의 인덱스
4. 더 큰 자식 선택
- cr <= right: 오른쪽 자식이 배열 범위 내에 있는지 확인
- arr[cr] > arr[cl]: 오른쪽 자식이 왼쪽 자식보다 크다면 cr을 선택, 아니면 cl 선택
- 즉, 더 큰 값을 가진 자식을 선택하여 child로 지정
5. 부모 노드가 더 크면 종료
- 부모(tmp)가 선택한 자식보다 크거나 같으면 힙 속성이 유지된 상태 → 종료
6. 부모를 자식의 값으로 교체 후 인덱스 변경
- 부모 노드의 값을 자식 노드의 값으로 변경
- parent를 child로 업데이트하여 다음 반복에서 검사할 위치를 변경
→ 아래로 내려가면서 힙 구조를 조정하는 과정
7. 최종 위치에 저장
- tmp를 최종적으로 적절한 위치에 배치
🚀 실행 예제
(Ex) [4, 10, 3, 5, 1] 배열을 힙으로 만드는 과정
i = 0, left = 1, right = 4
arr = [4, 10, 3, 5, 1]
1. tmp = 4, parent = 0
2. cl = 1, cr = 2
3. arr[1] = 10, arr[2] = 3 → child = 1 (더 큰 값 선택)
4. tmp(4) < arr → 교환
arr = [10, 10, 3, 5, 1] (임시적으로 중복된 값)
5. parent = 1 (이동)
6. cl = 3, cr = 4
7. arr[3] = 5, arr[4] = 1 → child = 3
8. tmp(4) < arr → 교환
arr = [10, 5, 3, 5, 1]
9. parent = 3 (이동), 더 이상 자식 없음 → 종료
10. 최종적으로 arr[3] = tmp(4) → arr = [10, 5, 3, 4, 1]heap_sort
def heap_sort(arr):
n = len(arr)
# 1. 최대 힙 생성 (힙 구조 만들기)
for i in range((n-1)//2, -1, -1):
heafity(arr, i, n-1)
# 2. 정렬 과정 (최대값을 하나씩 꺼내 정렬)
for i in range(n-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0] # 최대값을 배열의 끝으로 이동
heafity(arr, 0, i-1)
return arr🔍 코드 분석
1. 최대 힙을 구성
- (n-1)//2부터 0까지 역순으로 heafity를 호출해 배열을 최대 힙으로 변환
- (n-1)//2는 마지막 내부 노드의 인덱스로, 여기서부터 루트까지 내려가며 힙 속성을 유지
2. 정렬 과정
- 루트(최대값)를 배열의 끝과 교환
- 교환 후, 남은 요소들(i-1까지)에 대해 다시 heafity를 호출하여 힙 속성을 유지
🚀 실행 예제
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)[10, 5, 3, 4, 1] → [1, 5, 3, 4, 10]
[5, 1, 3, 4, 10] → [4, 1, 3, 5, 10]
[4, 1, 3, 5, 10] → [3, 1, 4, 5, 10]
[3, 1, 4, 5, 10] → [1, 3, 4, 5, 10]📌 정리
- 두 단계로 진행됨
- 배열을 최대 힙으로 변환
- 루트(최대값)과 배열 끝을 교환 후, 다시 힙 속성을 유지
- 시간 복잡도: O(n log n)
- 힙 구성: O(n)
- 정렬 과정에서 heafity 호출: O(log n) × n번 → O(n log n)
- 제자리 정렬(in-place sort), 추가 메모리 사용 없음