[Algorithm] 힙 정렬(Heap Sort) 알고리즘(Swift 구현)

[Algorithm] 힙 정렬(Heap Sort) 알고리즘(Swift 구현)

 

이전에 한 번 힙(Heap)에 대해 알아본 적이 있다. 얄팍한 지식으로 정리를 했었는데, 오늘은 그 자료구조 힙을 가지고 정렬을 하는 방법에 대해 알아볼 것이다.

 

2022.05.15 - [Computer Science] - [자료구조] Heap 기초 개념 알아보기(python)

[자료구조] Heap 기초 개념 알아보기(python)

 

 

1. 힙이란 무엇인가?

 

1) 힙의 정의

힙은 힙 성질을 만족하는 거의 완전한 트리인 특수한 트리기반의 자료구조이다.

'힙 성질'을 만족하는 '트리 기반'의 자료구조가 '힙'이다. 힙을 알기 위해서는 힙 성질과 트리에 대해 알고 있어야 할 것이다.

 

그림으로 표현하면 이런 식으로 연결이 되어 있는 트리모양으로 나타낼 수 있다. 힙 자체는 정렬된 구조가 아니다.

위의 그림은 '최대 힙'의 자료구조인데, 부모 노드가 항상 크다는 조건만 만족한다. 왼쪽의 자식 노드와 오른쪽 자식 노드가 클 수도 있고 작을 수도 있는 정렬되지 않은 모습을 보인다.

 

그렇지만, 항상 최상단에 있는 노드는 가장 크거나 가장 작다.

 

힙은 '우선순위 큐'를 위해 만들어진 자료구조이기도 하다.

우선순위가 높은 데이터가 먼저 빠져나가도록 하는 데이터구조가 우선순위 큐인데, 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산 등에 사용되는 우선순위 큐를 가장 효율적으로 구현하기 위해서 힙을 사용한다.

 

 

2) 힙 성질

 

그렇다면 힙 성질은 무엇일까?

위에서 거의 다 설명했다. 

 

부모 노드가 항상 크거나 같고(Max Heap) 작거나 같다(Min Heap)는 조건만 만족한다.

 

이것이 힙 성질이며, 이것을 만족해야 힙이라고 할 수 있는 것이다.

 

왼쪽 자식노드, 오른쪽 자식노드의 우선순위는 상관이 없다. 오직 부모, 자식 간의 노드 비교만 하여 저 성질을 만족하면 힙인 것이다.

 

또한 '완전 이진트리'라는 성질을 가지고 있다.

완전 이진트리
(1) 완전 이진트리는 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
(2) 마지막 레벨은 모두 차있지 않아도 되지만, 노드가 왼쪽에서 오른쪽으로 차례로 채워져야 한다.

 

정리하면 힙은 완전 이진트리이며, 부모 노드가 항상 크거나 같고, 작거나 같다는 성질을 가지고 있다.

 

3) 트리

 

트리는 노드와 간선으로 나타낼 수 있는 자료구조이다. 

 

위에서 보듯 힙은 트리로 나타낼 수 있다. 그림에서 보면, 오른쪽, 왼쪽 자식 노드만 가지고 있는데, 보통 힙은 '이진트리'를 사용하여 만들기 때문에 이러한 모습을 하고 있다. 대부분은 이진트리를 활용하여 힙을 만든다.

 

힙은 이진 탐색 트리와 비교될 수 있는데, '좌/우' 관계를 보장(Balanced Search Tree)하는 것과 '상/하' 관계를 보장(Heap)하는 것에서 차이가 있다. 이진 탐색 트리가 왼쪽 자식 노드가 부모 노드보다 작고, 오른쪽 자식 노드가 부모 보다 크기 때문에, 가장 낮은 레벨의 왼쪽 리프 노드가 작은 것이 보장이 되어 있다. 힙은 상하 관계를 보장하기에 최상단의 부모 노드가 가장 크거나 작은 값이 있다는 것이 보장되는 것이다.

 

 

2. 힙 연산

 

여러 가지가 있는데, 쉽게 생각하면 '삽입과 추출 그리고 생성'과 관련된 연산이라고 생각하면 될 것 같다.

 

 

 

1) BuildHeap 

 

완전 이진트리를 Heap 구조로 만드는 작업이다.

만약 힙을 배열로 표한한다면, 인덱스 N / 2번 원소부터 N번 까지는 리프 노드라고 할 수 있다.

 

리프 노드를 제외한 나머지 노드에 아래에서 설명할 Heapify를 수행하면, 힙 구조로 빌드할 수 있다.

 

func buildMaxHeap(_ array: [Int]) {
    var i = array.count / 2
    while i >= 1 {
        maxHeapify(i)
        i -= 1
    }
}

 

 

2) Heapify**

 

힙에서 가장 중요한 연산이다. 이것을 활용해서 다른 힙 연산을 실행한다.

이진트리에서 힙 속성을 유지하는 작업이다. 최상단 노드부터 아래 레벨로 내려가면서 작업을 한다.

 

/**
 현재 원소와 자식 노드 값을 비교
 */
func maxHeapify(_ element: Int) {
    var largest = element
    var left = 2 * element // Left Child Node
    var right = 2 * element + 1 // Right Child Node

    // Compare the current element with the value of the child node.
    if left <= array.count && array[left] > array[element] {
        largest = left
    }
    if right <= array.count && array[right] > array[largest] {
        largest = right
    }

    // if child node has larger value, replace it and proceed with Heapify from the exchangee child node
    if largest != element {
        array.swapAt(element, largest)
        maxHeapify(largest)
    }
}

 

 

3) Peek

 

Heap에서 최대값을 반환한다.

Max Heap일 경우, 루트 값이기 때문에 루트 값을 반환하는 것과 같다.

 

func peek(_ array: [Int]) -> Int {
    return array[1]
}

 

 

4) Extract

 

Heap에서 최대 요소를 '추출'하는 작업을 한다.

Max Heap의 경우 최댓값을 추출하고 나면 그 노드가 비게 되는데, 가장 마지막 원소를 루트 노드에 배치하고 Heapify 과정을 다시 수행해서 Heap이 Heap 성질을 만족할 수 있도록 하는 연산이다.

 

func extractMax() -> Int {
    if array.count == 0 {
        return 0
    }

    var maxValue = array[1]
    array[0] = array[array.count]

    maxHeapify(0)

    return maxValue
}

 

 

5) IncreaseValue

 

Max Heap에서 사용하는 작업이다. 어느 하나의 노드의 값을 증가시키는 작업을 한다.

만약 힙 성질을 만족하지 않는 경우, 힙 성질을 만족시키기 위해서 Heapify 작업을 해주어야 할 수도 있다.

 

/**
 index에 있는 노드 값을 value로 변경한다. 변경하려는 값이 현재 값 보다 작으면 안 된다.
*/
func increaseValue(_ index: Int, _ changeValue: Int) {
    if changeValue < array[index] {
        print("New value is less than current value.")
    }

    array[index] = changeValue
    var index = index

    // 부모 노드가 작으면 교환하고 힙 성질을 만족할 때까지 반복한다.
    while index > 1 && array[index / 2] < array[index] {
        array.swapAt(index / 2, index)
        index = index / 2
    }
}

 

 

6) Insert

 

힙에 요소를 삽입하는 작업이다. 힙의 마지막 자리에 최솟값을 삽입하고, 그 자리에 있는 원소에 IncreaseValue 함수를 호출하여 추가된 값을 삽입할 값으로 증가시키고 힙 속성을 유지한다.

 

func insertElement(_ value: Int) {
    array.append(value)
    increaseValue(array.count - 1, value)
}

 

 

7) Delete

 

increaseValue를 수행하여 삭제할 요소를 max 값으로 증가시키고 루트 노드에 위치시킨다. 그런 다음 extract를 수행하여 루트 노드의 값을 추출한다.

 

func deleteElement(_ index: Int) {
    increaseValue(index, Int.max)
    extractMax()
}

 

 

3. 힙 정렬

 

1) 힙 정렬의 방법

 

위에서 힙이 구성되고 연산을 하는 방법을 알아보았다. 그렇다면 이러한 힙을 가지고 어떻게 정렬에 활용할 수 있을까?

Heapify가 기본이 되는 '추출' 방식으로 정렬을 하면 될 것이다.

 

힙은 최대값 혹은 최솟값이 최상단 노드에 항상 있다고 보장이 된다. 그렇기에 최상단 노드를 빼서 하나씩 나열해 놓으면 정렬된 상태가 보장될 것이다. 빠진 자리를 Heapify 연산을 통해 다시 힙 성질을 만족할 수 있게 해 주고... 그것들을 반복해서 모든 노드들을 뽑아내면 정렬이 완료되는 것이다.

 

 

2) 힙 정렬의 과정

var array = [2, 3, 5, 6, 7] 배열이 힙정렬 되는 과정을 보자.

 

 

(1) 힙 성질을 만족하게 하도록 하기

배열이 트리로 만들어지고, 힙 성질이 만족하도록 배치가 된다.

 

(2) 최대값 추출

최댓값을 없애버리고, 기존 배열의 마지막이든 처음이든 정렬 순서에 따라 다시 배치한다.

이렇게!

 

(3) 힙 성질을 만족하게 하기

 

가장 마지막에 있는 원소를 최상단 노드로 올린다. 예시 그림에서는 3이 될 것이다.

그러면 6이 다시 최상단 노드에 배치가 될 것이다.

 

 

(4) 원소가 없을 때까지 반복

 

6이 배치 되었으므로, 6을 추출하고, 그러면 2가 다시 최상단 노드로 오게 되는데, 그러면 5와 자리가 바뀔 것이다. 5가 가장 마지막 원소이기 때문이다.

그런 다음 5를 추출하고.......

 

이렇게 반복을 하여 모든 노드를 없애준다.

 

 

3) 시간, 공간 복잡도

 

시간복잡도의 경우, 평균, 최선, 최악 모두  O(NlogN)이다. 완전 이진트리이기 때문에, logN 만큼의 높이를 가지고 있고 Heapify 연산이 logN 시간 안에 되기 때문에, 그것을 원소의 개수 N과 곱하면 NlogN이 나온다.

 

공간복잡도는 swap으로 해결하기 때문에 O(N)이다.

 

참고로 당연하게도 힙 정렬은 '불안정 정렬'에 속한다. (뭔가 복잡해 보이잖아...)

 

 

4. Swift 코드

func myMaxHeapSort(_ list: [Int], reversed: Bool = false) -> [Int]{
    var tempList = list
    var result: [Int] = []
    
    for i in stride(from: list.count - 1, to: -1, by: -1){
        if i == 0 {
            guard let last = tempList.popLast() else { fatalError() }
            result.append(last)
        } else {
            tempList = makeMaxHeap(tempList)
            let temp = tempList[0]
            tempList[0] = tempList[i]
            tempList[i] = temp
            guard let last = tempList.popLast() else { fatalError() }
            result.append(last)
        }
    }
    if reversed == false {
        result.reverse()
        return result
    } else {
        return result
    }
}

func makeMaxHeap(_ list: [Int]) -> [Int]{
    var result = list
    
    for i in 1..<list.count{
        var childNode = i
        repeat{
            let root: Int = (childNode - 1) / 2
            if result[root] < result[childNode]{
                let temp = result[childNode]
                result[childNode] = result[root]
                result[root] = temp
            }
            childNode = root
        } while (childNode != 0)
    }
    
    return result
}

print(myMaxHeapSort(makeMaxHeap([3,5,4,2,7,9,6]),reversed: true))

 

5. 정리

 

힙 정렬은 알고리즘 보다는 힙 자료구조 자체를 이해하고 있으면 저절로 생각나는 것이라고 할 수 있을 것 같다. 힙에 대해 오래 공부했는데, 벽에 막힌 것 같은 프로그래머스 레벨 2 풀이에도 도움이 많이 될 것 같다.

 

다음은 기수정렬을 알아보고 마지막으로 Tim Sort를 알아보도록 하자....