Swift. Heap

Choooose·2023년 3월 29일

heap swift

자료구조 / 알고리즘

목록 보기

4/4

Heap ( 힙 )

완전 이진 트리
부모와 자식간의 대소관계가 명확하다

힙의 종류

힙에는 최대힙과 최소힙이 있다.

최소힙은 부모노드의 키 값이 자식 노드보다 큰 힙이고 따라서 루트 노드가 가장 큰 값을 갖는다.

최대힙은 부모노드의 키 값이 자식노드보다 작거나 같은 힙이다. 따라서 루트 노드가 가장 작은 값을 갖는다.

힙의 표현

힙은 보통 배열로 표현한다.

연산을 편리하게 하기 위해서 배열의 0번 인덱스는 비워두고 1부터 루트노드로 채우게 된다.

그림으로 나타내면

위처럼 왼쪽에서 오른쪽으로 가면서 힙이 채워지게 된다.

또한 힙으로 나타낸 배열에서는
왼쪽 자식노드는 부모 노드의 인덱스 * 2 에 위치해 있고
오른쪽 자식노드는 부모노드의 인덱스 * 2 +1 에 위치해 있는 것을 알 수 있다.
또한 부모노드는 자식노드들의 인덱스 / 2 에 위치해 있다.

예를 들어 2번 인덱스에 위치한 노드 18 의 왼쪽 자식노드는 2 * 2 로 4번째 인덱스에 위치해 있음을 확인할 수 있다.

힙의 연산

힙의 연산에는 삽입(insert) 삭제(pop)가 있다.

먼저 삽입(insert)연산을 살펴보면

Insert

삽입 연산은 먼저 배열의 가장 마지막 원소로 삽입하려는 값이 들어간다.
아래의 그림을 예시로 들면 삽입할 값 17이 배열의 가장 마지막 인덱스인 5 자리에 들어가게 된다.

17이 부모노드인 15보다 크므로 15와 자리를 바꾸게 된다.
이때 바꾸는 방법은 17의 인덱스와 15의 인덱스를 Swap하는 방식인데 이때 앞서 말했듯이 자식노드의 인덱스 / 2 는 부모노드의 인덱스이므로 이러한 방법으로 인덱스를 찾고 Swap 한다.

Pop

힙의 삭제연산은 루트노드를 삭제한다.
따라서 최대힙의 경우에는 가장 큰값이 삭제되고 최소힙의 경우에는 가장 작은 값이 삭제된다.

최대힙을 예로들어 삭제과정은 먼저 삭제(루트)노드와 가장 마지막 리프노드를 바꾼다.
그 뒤에 삭제노드를 삭제한 뒤 루트노드에 자리잡은 리프노드를 자식노드들과 비교하면서
값이 큰 자식노드의 경우 Swap을 진행한다.

자식 노드보다 값이 크거나 더 이상 바꿀수 없는 리프노드 자리에 오면 연산을 종료한다.

삭제 연산에서 Swap의 경우의 수는 총 다섯가지이다.

자식 노드가 없는 경우
→ 이 경우는 루트노드와 하나의 자식으로 이루어져있는 힙이라고 볼 수 있다.
따라서 Swap을 할 필요가 없다.
왼쪽 자식노드만 있는 경우
→ 왼쪽 자식노드와 비교하여 자식노드가 큰 경우 Swap을 진행한다.

무조건 왼쪽 → 오른쪽으로 힙이 채워지기 때문에 오른쪽 자식노드만 존재할 수는 없다.
양쪽 모두 자식노드가 있지만 둘 다 작은 경우
→ Swap을 진행할 필요 없이 멈춘다.
양쪽 모두 자식노드가 있고 둘 다 큰 경우
→ 양쪽 자식노드 중 더 큰 값과 Swap한다.
양쪽 모두 자식노드가 있지만 왼쪽, 오른쪽 둘 중 하나만 큰 경우
→ 큰 값을 가진 자식노드와 Swap한다.

구현 코드

위의 Heap과 연산을 코드로 나타내면 아래와 같다.

힙 선언

		var heap = [element]()
    var count: Int {
        return heap.count
    }
    var isEmpty: Bool {
        return heap.isEmpty
    }

먼저 힙의 선언부분이다.
Heap은 배열로 선언하며 연산에 자주 쓰이는 힙의 크기와 힙이 채워져있는 여부를 선언했다.

삽입연산

mutating func insert(_ item: element) {
        if isEmpty {
            heap.append(item)
            heap.append(item)
            return
        }
        heap.append(item)
        var insertIndex = count - 1
        while heap[insertIndex] <= heap[insertIndex / 2] {
            if insertIndex <= 1 { break }
            
            let tmp = heap[insertIndex / 2]
            heap[insertIndex / 2] = heap[insertIndex]
            heap[insertIndex] = tmp
            insertIndex /= 2
        }
    }

힙이 비어있는 경우 1번 인덱스까지 item을 넣어주고 리턴한다.

위에서도 말했듯이 힙의 인덱스가 1부터 시작하고 현재는 제네릭 타입을 활용하였기에 0번째 인덱스에 들어갈 값을 고정시킬 수 없다.
따라서 처음에 들어갈 값을 0번째에도 넣어준다.

힙이 비어있지 않은 경우는

heap의 마지막 인덱스에 item을 넣어준다.
또한 새롭게 들어간 item의 인덱스를 부모 노드와 비교하며 더 큰 경우 Swap을 진행한다.
swift에서는 swapAt 이라는 함수를 제공하지만 직접 구현해보았다.

heap에 들어간 item이 더 이상 부모노드보다 크지 않으면 연산을 종료한다.

삭제 연산

mutating func pop() -> element? {
    if count <= 1 { return nil }
    
    let popValue = heap[1]
    heap[1] = heap[count-1]
    heap.removeLast()
    
    var popIndex = 1
    
    while true {
        let leftIndex = popIndex * 2
        let rightIndex = popIndex * 2 + 1
        if count <= 1 {
            return popValue
        }
        if leftIndex <= count-1 && heap[popIndex] < heap[leftIndex] {
            let tmp = heap[popIndex]
            heap[popIndex] = heap[leftIndex]
            heap[leftIndex] = tmp
            popIndex = leftIndex
        }
        if heap[popIndex] > heap[leftIndex] && heap[popIndex] > heap[rightIndex] {
            return popValue
        }
        if heap[popIndex] < heap[leftIndex] && heap[popIndex] < heap[rightIndex] {
            let biggerIndex = heap[leftIndex] < heap[rightIndex] ? rightIndex : leftIndex
            let tmp = heap[popIndex]
            heap[popIndex] = heap[biggerIndex]
            heap[biggerIndex] = tmp
            popIndex = biggerIndex
        }
    }
}

삭제 연산에서는 먼저 힙이 비어있지 않은지를 검사한다.
만약 비어있다면 nil을 리턴하도록 하기 위해 반환할 element를 옵셔널로 선언하였다.
비어있지 않다면 힙의 루트 노드를 popValue로 저장한 뒤에 가장 마지막 리프노드와 변경 후에 제거한다.
그뒤부터는 위에서 말했듯이 경우에 따라서 popIndex를 업데이트하면서 변경할 노드의 자식노드가 없거나 자식노드보다 큰 경우까지 힙을 정렬한다.

전체 코드

fileprivate struct Heap<element: Comparable> {
    var heap = [element]()
    var count: Int {
        return heap.count
    }
    var isEmpty: Bool {
        return heap.isEmpty
    }
    
    mutating func insert(_ item: element) {
        if isEmpty {
            heap.append(item)
            heap.append(item)
            return
        }
        heap.append(item)
        var insertIndex = count - 1
        while heap[insertIndex] <= heap[insertIndex / 2] {
            if insertIndex <= 1 { break }
            
            let tmp = heap[insertIndex / 2]
            heap[insertIndex / 2] = heap[insertIndex]
            heap[insertIndex] = tmp
            insertIndex /= 2
        }
    }
    
    mutating func pop() -> element? {
        if count <= 1 { return nil }
        
        let popValue = heap[1]
        heap[1] = heap[count-1]
        heap.removeLast()
        
        var popIndex = 1
        
        while true {
            let leftIndex = popIndex * 2
            let rightIndex = popIndex * 2 + 1
            if count <= 1 {
                return popValue
            }
            if leftIndex <= count-1 && heap[popIndex] < heap[leftIndex] {
                let tmp = heap[popIndex]
                heap[popIndex] = heap[leftIndex]
                heap[leftIndex] = tmp
                popIndex = leftIndex
            }
            if heap[popIndex] > heap[leftIndex] && heap[popIndex] > heap[rightIndex] {
                return popValue
            }
            if heap[popIndex] < heap[leftIndex] && heap[popIndex] < heap[rightIndex] {
                let biggerIndex = heap[leftIndex] < heap[rightIndex] ? rightIndex : leftIndex
                let tmp = heap[popIndex]
                heap[popIndex] = heap[biggerIndex]
                heap[biggerIndex] = tmp
                popIndex = biggerIndex
            }
        }
    }
}