힙 정렬(Heap sort) - 파이썬 코드 구현

Heap sort python code implementation
Heap sort 파이썬 코드를 작성해 보자.

---

힙 정렬(Heap Sort)

힙은 2진 트리인데, Min-heap(최소값이 루트 노드에 있음. 부모 노드가 자식 노드보다 작아야 함.)과 Max-heap(최대값이 루트 노드에 있음. 부모 노드가 자식 노드보다 커야 함.)

위키 피디아의 설명을 참고해 보자.

1. n개의 노드에 대한 완전 이진 트리를 구성한다. 이때 루트 노드부터 부모노드, 왼쪽 자식노드, 오른쪽 자식노드 순으로 구성한다.

2. 최대 힙을 구성한다. 최대 힙이란 부모노드가 자식노드보다 큰 트리를 말하는데, 단말 노드를 자식노드로 가진 부모노드부터 구성하며 아래부터 루트까지 올라오며 순차적으로 만들어 갈 수 있다.

3. 가장 큰 수(루트에 위치)를 가장 작은 수와 교환한다.

4. 2와 3을 반복한다.

힙은 다음과 같이 구성된다.

Max heap를 단계를 나누어 간단하게 설명하면,

1. 이진 트리로 구성된 힙에서, 루트 노드와 제일 마지막 노드의 순서를 교환해 준 다음, 루트 노드에 있는 녀석을 heapify를 이용해서 자신의 자리를 찾도록 한다. 이때, max-heap의 원래 루트는 최댓값이 되므로, 배열의 최댓값을 구한 것이다.
2. 길이가 1 줄어든 힙을 가지고 1의 과정을 반복하면, 각 iteration마다 배열의 최댓값이 정렬된 자리를 찾아간다.

그림으로 보면 이렇다.

이제 파이썬 코드를 짜보도록 하자.

# Insertion sort implementation
import sys #for sys.maxsize
from random import randrange
import math
import time

#
# Helper functions
#
# swap, print_array
#

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]

def print_array(input):
    for i in range(len(input)):
        print(input[i], end=' ')
    print()    

#
# Main sorting function : 
#

def heapify(Arr, index, arr_size):
    if arr_size // 2 - 1 < index:
        if Arr[(index-1) // 2] < Arr[index]:
            swap(Arr, (index-1)//2, index)
            heapify(Arr, (index-1)//2, arr_size)
    else:
        if Arr[2*index + 1] > Arr[index] or \
            (2*index+2) <  arr_size and \
                Arr[2*index + 2] > Arr[index]:
            if (2*index+2) >= arr_size or \
                Arr[2*index + 1] > Arr[2*index + 2]:
                swap(Arr, index, 2*index + 1)
                heapify(Arr, 2*index + 1, arr_size)
            else:
                swap(Arr, index, 2*index + 2)
                heapify(Arr, 2 * index + 2, arr_size)


def heap_sort(Arr, arr_size):

    for i in range(len(Arr) // 2, -1, -1):
        heapify(Arr, i, len(Arr))

    for i in range(len(Arr) - 1, -1, -1):
        swap(Arr, i, 0)
        heapify(Arr, 0, i)


f = open("insert_dataset.txt", 'w')

for i in range(100):
    array_t = []
    for j in range(100):
        array_t.append(randrange(sys.maxsize))
    start = time.process_time()
    heap_sort(array_t, len(array_t)-1)
    end = time.process_time()
    f.write(str((end - start) * 1000000) + "\n")

# print("Elasped time : " + str(end-start))

f.close()