[알고리즘] 힙 정렬

힙 정렬이란?

최대 힙 트리나 최소 힙 트리를 구성해서 정렬하는 방법으로 기본적으로는 1차원 배열을 사용하여 구현하는 방식이다.

내림차순 정렬을 할 때에는 최소 힙 트리를 구성하고, 오름차순 정렬을 할 때에는 최대 힙 트리로 구성한다.

---

힙 정렬 알고리즘의 구현

힙은 최상위 루트 노드로부터 시작하는 완전 이진 트리이다. 이 루트 노드에서 왼쪽과 오른쪽으로 각각 노드가 존재하고, 루트 노드를 부모 노드, 왼쪽 및 오른쪽 노드를 자식노드라고 말한다.

부모노드의 인덱스가 i라고 한다면 왼쪽 자식노드는 2 * i 위치에 존재하고, 오른쪽 자식 노드는 2 * i + 1의 위치에 존재한다.

 

이진 트리를 만들면서 최대 힙, 자식 노드를 가지는 부모 노드를 구성해나가면서 점점 루트로 올라오는 순차적 단계를 이용하여 만들어 낼 수 있다.

이 후 루트노드에 존재하는 가장 큰 수와 맨 아래 존재하는 가장 작은 수를 교환하고, 위의 방식을 계속 반복하는 식으로 구현할 수 있다.

 

간단하게 설명해서 값을 넣을 때 부모 노드보다 자식 노드의 값이 크다면 서로 바꿔주면서 배열에 넣은 뒤 순차적 단계로 루트값과 맨 아래 값을 서로 바꿔주고, 힙의 크기를 줄여가면서 계속 수행한다면 배열에 있는 값을 원하는 순서로 정렬할 수 있게 된다.

 

다음 코드는 과제를 수행하면서 작성한 노래 플레이리스트를 정렬한 문제이다.

class Song:
    def __init__(self, title, artist, duration):
        self.title = title
        self.artist = artist
        self.duration = duration

    def __str__(self):
        return f"{self.title} by {self.artist}, Duration: {self.duration} seconds"

# 힙 정렬을 위한 heapify 함수
def heapify(songs, n, i, key):
    largest = i  # 루트를 가장 큰 값으로 초기화
    l = 2 * i + 1  # 왼쪽 자식 = 2*i + 1
    r = 2 * i + 2  # 오른쪽 자식 = 2*i + 2

    # 왼쪽 자식이 루트보다 크다면 (insert code)
    # 왼쪽과 비교한다. key값에 따라 확인한 후 왼쪽 자식이 크다면 largest로 교체해준다.
    if l < n and getattr(songs[i], key) > getattr(songs[largest], key):
        largest = l

    # 오른쪽 자식이 루트보다 크다면 (insert code)
    # 오른쪽과 비교한다. key값에 따라 확인한 후 오른쪽 자식이 크다면 largest로 교체해준다.
    if l > n and getattr(songs[i], key) > getattr(songs[largest], key):
        largest = r

    # 루트가 변경되었다면 (insert code)
    # 최댓값이 정해졌으므로 마지막과 루트를 바꾼다.
    if largest != i:
        songs[largest] = songs[i]
        songs[i] = songs[largest]

    # 힙 속성을 다시 맞춤 (insert code)
    # 바꾸는 작업을 수행하였기 때문에 다시 정렬을 실시한다.
        heapify(songs, n, largest, key) 

# 힙 정렬 함수
def heap_sort(songs, key):
    n = len(songs)

    # 맥스 힙 생성
    for i in range(n // 2 - 1, -1, -1):
        #insert code
        # 부모노드가 자식노드보다 크게 만들기 위해 아래서부터 시작하는 방식으로 생성한다.
        heapify(songs, n, i, key)

    # 요소를 하나씩 추출하여 정렬
    for i in range(n - 1, 0, -1):
        songs[i], songs[0] = songs[0], songs[i]  # swap
        #insert code
        # 바뀌었기 때문에 다시 수행하여준다.
        heapify(songs, i, 0, key)

# 메인 함수
def main():
    songs = []
    n = int(input("Enter the number of songs: "))

    # 곡 데이터 입력
    for _ in range(n):
        title = input("Enter the song title: ")
        artist = input("Enter the artist name: ")
        duration = int(input("Enter the song duration in seconds: "))
        songs.append(Song(title, artist, duration))

    # 정렬 기준 선택
    print("\nChoose sorting criteria:")
    print("1. Title")
    print("2. Artist")
    print("3. Duration")
    choice = int(input("Enter choice (1/2/3): "))

    if choice == 1:
        key = 'title'
    elif choice == 2:
        key = 'artist'
    elif choice == 3:
        key = 'duration'
    else:
        print("Invalid choice")
        return

    # 힙 정렬 수행
    heap_sort(songs, key)

    # 정렬된 플레이리스트 출력
    print("\nSorted Playlist:")
    for song in songs:
        print(song)

if __name__ == "__main__":
    main()

---

힙 정렬의 시간복잡도

힙을 배열시킬 때 사용한 heapify 함수는 정렬을 수행하면서 largest값이 변할 경우 자신을 호출하는 재귀 방식으로 구현되어 있다.

전체 노드의 개수가 n이고 높이가 h, 자식노드가 최대 2개로 구성되어 있는 힙을 계산식으로 표현하면 h = log2n이다.

그러므로 heapify 함수의 시간 복잡도는 O(log n)으로 수행되지만, 최대 n개의 데이터를 삭제하거나 재구성 시간을 포함하기 때문에 O(n log n)의 시간복잡도를 가진다고 할 수 있다.