Swift 힙(Heap) 구현

Heap

• Heap이란 완전이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.
• 여러 가지의 값 중, 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조이다.
• 중복값을 허용한다.

완전이진트리

- 마지막 레벨을 제외하고 모든 레벨에 노드가 꽉 차있다.

- 자식노드는 최대 2개만 가질 수 있고, 노드가 왼쪽부터 채워져야 한다.

- 배열을 사용한 표현이 가능하다.

 

 

 

Swift로 Heap 구현

• 힙을 저장하는 자료구조는 배열이다.
• 쉽게 구현하기 위해 배열의 첫 번째 인덱스인 0은 사용하지 않는다.
• 코드로 보기 전에 Heap의 성질들을 본다.
• 힙은 구조체로 구현한다.

struct Heap<T: Comparable> {
	// 힙의 원소를 넣을 배열 선언
    // 최대힙,최소힙 정렬함수 선언
    private var elements: [T] = []
    private let sortFunction: (T,T) -> Bool
    
    // 힙의 인덱스 0 은 사용하지 않는다
    // 인덱스 0의 값만 있으면 비어있다고 판단
    var isEmpty: Bool {
        return elements.isEmpty || elements.count == 1
    }
    
    // 루트노드의 원소 출력
    var peek: T? {
        if self.elements.isEmpty { return nil}
        return self.elements[1]
    }
    
    // elements[0]을 제외한 원소갯수
    var count: Int {
        if elements.isEmpty {
            return 0
        } else {
            return elements.count - 1
        }
    }
    
    // buildHeap() 함수는 힙의 재구성 함수
    // 인덱스0은 사용하지 않으므로 임의의 값 넣어서 칸 차지하기
    init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFunction
        if elements.count > 1 {
            self.buildHeap()
        }
    }
}

// 처음 힙이 선언되었을때 정렬함수를 통해 힙을 구성하는 함수이다.
// diveDown 함수는 입력된 index의 자식노드들과 정렬함수를 통해 값 비교 후 교환하는 함수이다.
// self.element.count / 2 는 노드중 자식노드를 가진 노드들을 전부 탐색한다.

	mutating func buildHeap() {
        for index in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: index)
        }
    }

 

사진 출처: https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 

부모 노드와 자식 노드의 관계

왼쪽 자식 index = (부모 index) * 2
오른쪽 자식 index = (부모 index) * 2 + 1
부모 index = (자식 index) / 2

    // 왼쪽자식노드의 인덱스
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    // 오른쪽자식노드의 인덱스
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    // 부모노드의 인덱스
    func parent(of index: Int) -> Int {
        return index / 2
    }

 

힙의 삽입

1. 새로운 노드를 넣을 때, 배열의 마지막에 넣는다.

2. 새로운 노드를 부모노드와 비교하여 교환한다.

3. 부모노드는 새로운 노드의 index / 2 이므로 서로 swap 한다.

 

    // 힙이 비어있다면, 노드 추가 2번 (첫번째 인덱스를 1로 갖기 위해)
    // 힙이 비어있지 않다면 배열의 마지막에 노드 추가
    // 최대힙, 최소힙 정렬기준에따라 추가된 노드와 부모노드 비교 및 교환
    mutating func insert(element: T) {
        if self.elements.isEmpty {
            self.elements.append(element)
            self.elements.append(element)
            return
        }
        self.elements.append(element)
        self.swimUp(from: self.elements.endIndex - 1)
    }

// 힙의 정렬기준 sortFuction에 따라 부모노드와 자식노드 교환
	mutating func swimUp(from index: Int) {
        var index = index
        while index != 1 && self.sortFunction(self.elements[index], self.elements[self.parent(of: index)]) {
            self.elements.swapAt(index, self.parent(of: index))
            index = self.parent(of: index)
        }
    }

 

힙의 삭제

1. 힙의 루트노드를 마지막 원소와 바꾼다. swap

2. 마지막원소를 꺼내고 루트노드부터 자식노드와 교환한다.

3. 힙을 재구성한다.

 

 // 삭제할 루트노드 출력
 // 루트노드와 마지막노드를 바꾼후, 마지막 노드를 꺼낸다.
 // 루트노드를 자식노드들과 정렬기준으로 교환
 	mutating func remove() -> T? {
        if self.elements.isEmpty { return nil}
        self.elements.swapAt(1, self.elements.endIndex - 1)
        let deleted = self.elements.removeLast()
        self.diveDown(from: 1)

        return deleted
    }

// 자식노드들의 인덱스를 가져와 부모노드와 정렬함수를 통해 값 비교후 교환한다.
// 부모노드가 정렬기준으로 자리를 찾을 때 까지 계속 자식노드들과 비교후 교환한다.
	mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)

        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }

        if higherPriority != index {
            self.elements.swapAt(index, higherPriority)
            self.diveDown(from: higherPriority)
        }
    }

 

힙의 시간복잡도 ( O(logn) )

- 배열의 최대 최소를 구하면 O(n)이 걸렸지만, 힙에 넣고 정렬한다면 더 빠르게 찾을 수 있다.

 

 

Heap 구현 코드

+ index 계산을 위해 첫 원소의 인덱스값을 1로 설정하므로 이에 IsEmpty와 insert부분 수정

import Foundation

struct Heap<T: Comparable> {
    var elements: [T] = []
    var sortFunction: (T,T) -> Bool
    var isEmpty: Bool {
        return elements.isEmpty || elements.count == 1
    }
    var peek: T? {
        if elements.isEmpty {
            return nil
        } else {
            return elements[1]
        }
    }
    var count: Int {
        if elements.isEmpty {
            return 0
        } else {
            return elements.count - 1
        }
    }
    init(elements: [T] = [], sortFunction: @escaping (T,T) -> Bool) {
        if !elements.isEmpty {
            self.elements = [elements.first!] + elements
        } else {
            self.elements = elements
        }
        self.sortFunction = sortFunction
        if elements.count > 1 {
            self.buildHeap()
        }
    }
    func leftChild(of index: Int) -> Int {
        return index * 2
    }
    func rightChild(of index: Int) -> Int {
        return index * 2 + 1
    }
    func parent(of index: Int) -> Int {
        return index / 2
    }

    mutating func swimUp(from index: Int) {
        var idx = index
        while idx != 1 && self.sortFunction(self.elements[idx], self.elements[parent(of: idx)]) {
            self.elements.swapAt(idx, self.parent(of: idx))
            idx = self.parent(of: idx)
        }
    }
    mutating func insert(element: T) {
        if self.elements.isEmpty {
            self.elements.append(element)
            self.elements.append(element)
            return
        }
        self.elements.append(element)
        self.swimUp(from: self.elements.endIndex - 1)
    }
    mutating func diveDown(from index: Int) {
        var higherPriority = index
        let leftIndex = self.leftChild(of: index)
        let rightIndex = self.rightChild(of: index)

        if leftIndex < self.elements.endIndex && self.sortFunction(self.elements[leftIndex], self.elements[higherPriority]) {
            higherPriority = leftIndex
        }
        if rightIndex < self.elements.endIndex && self.sortFunction(self.elements[rightIndex], self.elements[higherPriority]) {
            higherPriority = rightIndex
        }
        if higherPriority != index {
            self.elements.swapAt(index, higherPriority)
            self.diveDown(from: higherPriority)
        }
    }
    
    mutating func buildHeap() {
        for i in (1...(self.elements.count / 2)).reversed() {
            self.diveDown(from: i)
        }
    }
    mutating func remove() -> T? {
        if self.isEmpty {
            return nil
        }
        self.elements.swapAt(1, self.elements.endIndex - 1)
        var returnValue = self.elements.removeLast()
        self.diveDown(from: 1)
        
        return returnValue
    }
}