Heap Sort 구현(파이썬)

이번 글에서는 Heap sort를 구현해볼 것이다. 

 

heap은 max heap을 사용할 것이다. 

 

우리는 배열에 데이터를 넣고 heap으로 사용할 것이다. 

 

이전 글에서 우리는 배열로 complete binary tree를 만들때 부모노드를 구하는 방식을 배웠다.

 

여기서 자식노드를 구하고 싶을 경우

• 왼쪽 자식노드: 부모노드 index x 2
• 오른쪽 자식노드: 부모노드 index x 2 + 1

이 공식은 배열의 0번째 index가 비워져 있을 때의 공식이다. 

 

배열을 모두 채웠을 경우는 공식이 아래와 같아진다. (한칸씩 배열이 왼쪽으로 밀림)

 

• 부모 = 배열의 길이 // 2 - 1
• 왼쪽 자식 = 부모 * 2 + 1
• 오른쪽 자식 = 왼쪽 자식 +1

우리는 이 공식을 이용하여 힙 정렬을 구현할 것이다. 

 

우리는 가장 오른쪽 아래의 부모 노드부터 탐색할 것이다. 

 

배열의 길이 //2 -1 을 하게되면 마지막 부모 노드가 나온다. 

 

이 위치를 사용하여 코드를 구성할 것이다. 

 

코드의 작동방식은 다음과 같다. 

 

max heap

 

1. 가장 마지막 부모 노드부터 root 노드까지 반복하여 탐색

2. 현재 위치의 노드가 부모 노드인지 확인 -> 맞다면 계속 반복(자식과 크기 비교)

3. 자식 비교 -> 숫자가 더 큰 자식을 부모와 비교

4. 부모보다 크다면 부모와 위치를 바꾼 뒤 자식의 위치부터 다시 탐색

-> 자식의 위치에는 부모 데이터가 들어가 있음 ( 이 위치가 맞는지 재 탐색 해야함 )

5. 다시 2번부터 시작

 

heap sort

 

1. 배열의 길이부터 하나씩 줄여나가는 for문을 만듬 변수는 arr_len

-> arr_len은 위치 변경이 가능한 배열의 최대 길이임 ( 확정된 위치는 변경하지 않기 위함 )

2. 주어진 배열을 max heap으로 만듬

3. 첫번째 data를 마지막 data와 바꿈 ( 가장 큰 값을 맨 뒤로 )

4. 1번부터 반복

 

---

구현 코드 

def heapify(arr_len, arr): # max heap 구현
    last_parent = arr_len//2 - 1 # 가장 마지막 순서의 parent
    for current in range(last_parent, -1, -1): # current node를 last_parent부터 놓고 탐색
        while current <= last_parent: # current가 leaf node가 아닌지 check
            child = current*2 +1 # parent의 왼쪽 child
            sibling = child + 1 # parent의 오른쪽 child
            if sibling < arr_len and arr[sibling] > arr[child]: # array 길이 안에 있고 오른쪽 child가 왼쪽보다 큰 경우
                child = sibling # child 값을 더 큰 값으로 바꿈
            if arr[current] < arr[child]: # child가 부모 node인 current보다 클 때
                arr[current], arr[child] = arr[child], arr[current] # 두 값을 바꿔준다.
                current = child # 바꿔진 부모노드의 data 위치가 맞는지 확인해야 한다. -> current를 바뀐 부모 노드 데이터 위치로 바꿔줌
            else:
                break


def heap_sort(arr):
    for arr_len in range(len(arr), 1, -1): # 위치변경 허용 범위를 1씩 낮추고 있음 -> 순서 정해진 데이터를 놔두기 위함
        heapify(arr_len, arr) # 0번째 인덱스에 가장 큰 값
        arr[0], arr[arr_len-1] = arr[arr_len-1], arr[0] # 가장 큰 값을 위치 허용범위의 마지막 위치로 보내줌


arr = [1, 3, 5, 7, 9, 11, 13, 15, 14, 12, 10, 8, 6, 4, 2]
heap_sort(arr)

print(arr)

 

실행결과