[Swift] Array를 이용한 Heap 구현 3 - 함수형 프로그래밍

힙에 대한 배경 지식 및 구현은 아래 포스팅들을 참고하면 된다. 

https://taeminator1.tistory.com/43

https://taeminator1.tistory.com/44

 

길고 긴 여정이었지만, 이제 힙에 대한 구현은 마지막 포스팅이 될 것 같다. 이번 포스팅의 주제는 "다양한 힙 구현하기"이다. 지난 포스팅에서는 "최대 힙"을 구현했지만, 때로는 다른 종류의 힙을 원할 수도 있다. 

 

먼저 최소 힙을 구현하는 방법에 대해 생각해 보자. 간단히 설명하자면, 최소 힙(Min Heap)은 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 말한다. 이러한 힙을 구현하기 위해서는 아래와 같이 이전에 구현한 Heap 클래스에서 몇 개의 부등호의 방향만 변경해 주면 된다. 

func insert(data: Element) {
    ...

    // data와 getParent(at: index)!.getData() 간의 부등호 방향 변경(> 에서 < 로)
    while index > 0 && HeapNode(data) < getParent(at: index)! {
        ...
    }

    ...
}

@discardableResult func remove(at index: Int = 0) -> HeapNode<Element>? {
    ...

    while cIndex < count {
        // getLeftChild(at: pIndex)!와 getRightChild(at: pIndex)! 간의 부등호 방향 변경(< 에서 > 로)
        if cIndex < count - 1 && getLeftChild(at: pIndex)! > getRightChild(at: pIndex)! {
            ...
            }
    }
    // lastHeapNode와 hNodes[cIndex] 간의 부등호 방향 변경(>= 에서 <= 로)
    if lastHeapNode <= hNodes[cIndex] { break }
    
    ...
}

단 세 개의 부등호 수정으로 최소 힙이 구현되었다.

 

실제로 다음과 같이 최대 힙과 최소 힙을 구현할 수 있다. 

1. 부등호 세 개를 위해 클래스를 코드를 복사해, MaxHeap 클래스와 MinHeap 클래스를 따로 구현해주면 될 것이다. 그러면 코드의 양은 두 배로 늘고, 수정이라도 요구되는 날에는 각각의 클래스에서 전부 수정을 해줘야 해서 더할 나위 없이 좋을 것이다. 
2. 아니면 Heap이라는 클래스에서 insertForMaxHeap과 insertForMinHeap을 따로 구해주고, removeForMaxHeaprhk removeForMaxHeap을 따로 구해주어 클래스의 길이를 늘려 멋지게 만드는 것이 좋을 것이다. 

하지만 두 방법 모두 반복되는 코드의 양이 많아 가독성이 떨어지고, 유지 보수하는데 큰 어려움이 있다. 

 

이러한 점들을 고려해 하나의 클래스를 이용해 최대 힙과 최소 힙에 대한 인스턴스를 모두 만들 수 있는 방법을 살펴보자. 총 두 가지 방법으로 구현하였다. 

 

[클래스에서 최대/최소 힙을 선택할 수 있도록 속성을 추가하는 방법]

이 전 포스팅에서 구현한 Heap 클래스를 수정하여 구현했다. (편의상 클래스 이름을 Heap2라고 명명하였다)

 

먼저 Heap 클래스에 다음과 같이 isMaxHeap이라는 저장 속성을 추가한다. 

class Heap2<Element: Comparable> {
    ...
    var isMaxHeap: Bool                // Max Heap인지 Min Heap인지 결정
    
    init(isMaxHeap: Bool = true) {
        self.isMaxHeap = isMaxHeap
    }
}

해당 속성을 이용해 삭제/삽입 메서드 내부에서 분기를 해주어도 되지만, 그러면 앞에서 설명한 두 가지 방법과 다를 게 없다고 생각하여 비교를 위한 함수를 따로 정의해 주었다. 

extension Heap2 {
    func isLhsBigger<T: Comparable>(lhs: T, rhs: T, isSameOK: Bool) -> Bool {
        if isSameOK && lhs == rhs  { return true }
        
        if isMaxHeap    { return lhs > rhs }
        else            { return rhs > lhs }
    }
}

눈여겨봐야 하는 부분이 하나 있다. 바로 부등호의 방향이다. 이전에 최대 힙과 최소 힙을 구현했을 때 부등호만 달리 해주면 된다고 설명을 했다. 근데 >의 대응되는 부등호의 방향은 <=가 아닌 <이다. 마찬가지로 >=에 대응되는 부등호의 방향은 <가 아니라 <=이다. 다시 말해, 등호는 그대로 가져가고, 부호의 방향만 바뀌는 것이다. 해당 사항을 고려하여, isSame이라는 매개변수를 추가했고, 부호의 방향만 바꿀 수 있도록 구현하였다. 

 

그러고 나서 해당 함수를 노드의 비교가 이뤄지는 곳에서 다음과 같이 사용하면 된다. 

func insert(data: Element) {
    ...

    // isLhsBigger 함수를 이용해 비교
    while index > 0 && isLhsBigger(lhs: data, rhs: getParent(at: index)!.getData(), isSameOK: false) {
        ...
    }

    ...
}

@discardableResult func remove(at index: Int = 0) -> HeapNode<Element>? {
    ...

    while cIndex < count {
        // isLhsBigger 함수를 이용해 비교
        if cIndex < count - 1 && isLhsBigger(lhs: getRightChild(at: pIndex)!, rhs: getLeftChild(at: pIndex)!, isSameOK: false) {
            ...
        }
    }
    // isLhsBigger 함수를 이용해 비교
    if isLhsBigger(lhs: lastHeapNode, rhs: hNodes[cIndex], isSameOK: true) { break }
    
    ...
}

이렇게 수정한 Heap2 클래스는 다음과 같이 인스턴스를 만들 수 있다. 

var maxHeap: Heap2 = Heap2<Int>(isMaxHeap: true)          // 최대 힙
var minHeap: Heap2 = Heap2<Int>(isMaxHeap: false)         // 최소 힙

 

이제는 하나의 클래스로 최대 힙과 최소 힙을 구할 수 있게 되었다. 그렇다면 다음과 같은 조건의 힙들을 원하다면 어떻게 해야 할까. 

• "자식 노드의 값이 부모 노드의 값 보다 0으로부터 멀리 떨어진 힙"

앞에서 구현한 Heap 클래스로는 해당 Heap을 만들 수 없다. 

 

[클래스에서 함수 속성을 추가하는 방법]

Swift가 프로그래밍의 패러다임 측면에서 가장 큰 특징 중에 하나는 함수형 프로그래밍 언어라는 점이다. 함수형 프로그래밍 언어는 이름에서 알 수 있듯이, 함수를 다양하게 활용할 수 있는 방법을 제공한다는 특징이 있다. 함수를 다양하게 활용할 수 있는 방법에는 다음과 같은 것들이 있다. 

• 함수를 변수에 저장할 수 있다. 
• 함수를 함수의 매개변수로 전달할 수 있다. 
• 함수를 함수의 반환 값으로 사용할 수 있다. 

이번에는 이러한 함수형 프로그래밍 언어의 특징을 이용해서 Heap 클래스를 구현해 보고자 한다. 이 전 포스팅에서 구현한 Heap 클래스를 수정해서 구현했다. (편의상 클래스 이름을 Heap3라고 명명하였다)

 

먼저 Heap 클래스에 다음과 같이 handler라는 함수 타입((HeapNode<Element>, HeapNode<Element>) -> Bool)을 갖는 속성을 let을 이용해 선언해 준다. 해당 속성은 한 번 초기화되면(힙의 종류가 한 번 결정되면) 변경될 일이 없기 때문에 let으로 선언해 주었다. 그리고 난 다음, init함수에 해당 handler 속성에 대한 초기화 구문을 추가한다. 기본 값은 클로저 표현식을 이용해 Max Heap이 되도록 정의하였다. 

class Heap3<Element: Comparable> {
    ...
    let handler: (HeapNode<Element>, HeapNode<Element>) -> Bool
    
    init(handler: @escaping (HeapNode<Element>, HeapNode<Element>) -> Bool = { $0 > $1 }) {
        self.handler = handler
    }
}

그다음 아래와 같이 힙 노드의 값을 handler를 이용하여 비교해주면 끝이다. 

func insert(data: Element) {
    ...

    // handler 함수를 이용해 비교
    while index > 0 && handler(HeapNode(data), getParent(at: index)!){
        ...
    }

    ...
}

@discardableResult func remove(at index: Int = 0) -> HeapNode<Element>? {
    ...

    while cIndex < count {
        // handler 함수를 이용해 비교
        if cIndex < count - 1 && handler(getRightChild(at: pIndex)!, getLeftChild(at: pIndex)!) {
            ...
        }
    }
    // handler 함수를 이용해 비교
    if lastHeapNode == hNodes[cIndex] || handler(lastHeapNode, hNodes[cIndex]) { break }
    
    ...
}

방금 전에 구현한 Heap 클래스와 같이 변수(isMaxHeap)와 함수(isLhsBigger)를 따로 구현해줄 필요 없이 handler 함수만 정의해주고 적용해주면 끝이다. 

 

이렇게 수정한 Heap3 클래스는 다음과 같이 인스턴스를 만들 수 있다. 

var maxHeap: Heap3 = Heap3<Int>(handler: < )              // 최대 힙
var minheap: Heap3 = Heap3<Int>(handler: > )              // 최소 힙
var someHeap: Heap3 = Heap3<Int>(handler: {               // 기타 힙
    abs($0.getData()) < abs($1.getData())
})

 

someHeap에 대한 연산을 아래와 같이 확인한 결과 원하는 대로 잘 동작했다. 

이제 인스턴스를 생성할 때, 함수를 매개변수로 전달하여 Bool을 반환한다면 어떠한 조건에 대한 힙도 만들 수가 있게 되었다. 

 

3번의 시간에 거쳐 드디어 Heap에 대한 구현이 끝났다. 생각보다 긴 여정이었지만, 프로그램을 다양한 각도로 설계해볼 수 있어서 좋았다.