Today I Learned

2022.10.10 (월)

힙이란?

힙 트리는 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리로, 짧게 힙이라고 줄여서 부르기도 합니다. 힙은 완전 이진 트리의 형태를 띠어야 하고, 부모의 값은 항상 자식들의 값보다 크거나 작아야합니다. 따라서 루트 노드는 자식 노드보다 항상 크거나 작기 때문에 최댓값, 최솟값은 항상 O(1) 안에 찿을 수 있습니다.

왜 항상 완전 이진트리여야 하나요?

단순히 최댓값, 최솟값을 O(1)안에 찾기 위해, "항상 완전 이진 트리 형태"일 필요는 없습니다. 완전 이진 트리를 사용하는 이유는 삽입하거나 삭제할 때의 속도떄문입니다.

시간 복잡도

데이터의 삽입과 삭제의 시간복잡도는 모두 **O(logN)**입니다.

Swift로 구현해보기

완전 이진트리의 자료구조는 배열이 됩니다. 따라서 배열의 index를 트리로 나타내는 방법을 알아야 합니다. 부모노드의 번호가 1이라고 할 때, 왼쪽 자식노드와 오른쪽 자식 노드의 Index는 2와 3으로 아래의 식을 가집니다.

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

다른 식으로도 표현할 수 있습니다. (index가 0부터 시작일 때)

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

그럼 먼저 Heap 구조체를 만들겠습니다.

struct Heap<T: Comparable> {
    var tree: [T] = []

    init(withData data: T) {
        tree.append(data)
        tree.append(data)
    }
}

Comparable 프로토콜을 준수하는 이유는 부모와 자식노드의 값을 비교하기 때문입니다. 또한, 초기화할 때 data를 두번 삽입하는 이유는 배열의 0번 index는 사용하지 않기 때문에 아무 의미없는 값을 채워넣기 위함입니다.

0부터 시작할 경우, 한 번만 삽입합니다.

데이터의 삽입

맥스 힙의 경우만 생각해 볼 때, 아래의 과정을 따릅니다.

가장 끝의 자리에 노드를 삽입한다.
그 노드와 부모 노드를 서로 비교한다.
노드가 부모 노드보다 크다면 서로 값을 교환한다.
부모 노드가 가장 클 때까지 2~3번 과정을 반복한다.

    mutating func insert(_ data: T) {
        // 비었다면 초기화가 필요합니다.
        if tree.isEmpty {
            tree.append(data)
            tree.append(data)
          	return 
        }

        // 가장 뒤에 노드를 삽입합니다
        tree.append(data)

        var newNodeIndex = tree.count - 1
        var parentNodeIndex = newNodeIndex / 2
        while tree[parentNodeIndex] < tree[newNodeIndex] {
            tree.swapAt(parentNodeIndex, newNodeIndex)
            newNodeIndex = parentNodeIndex
            parentNodeIndex = newNodeIndex / 2

            // 현재 노드가 루트노드이면 더이상 비교하지 않습니다.
            if newNodeIndex == 1 { break }
        }
    }

tree안에 아무 값도 존재하지 않을 때 insert가 된다면 초기화할 때처럼 0번 인덱스에 쓸모없는 값을 채워줘야 합니다. 값이 있다면, 마지막에 값을 삽입하고 2~3번의 과정을 반복합니다. 트리의 루트 노드의 index는 1이므로 쓸모없는 값이 들어있는 index인 0으로 가지 않도록 탈출 조건을 넣어줘야 합니다.

데이터의 삭제

데이터의 삭제는 최댓값인 루트노드를 제거합니다.

루토 노드를 제거한다.
루트 노드 자리에 가장 마지막 노드를 삽입한다.
루트자리에 올라간 마지막 노드와 자식 노드를 비교한다.
아래 조건을 따른다.
1. 부모보다 더 큰 자식이 없다면 교환하지 않고 끝낸다.
2. 부모보다 더 큰 자식이 하나만 있으면 그 자식하고 교환한다.
3. 부모보다 더 큰 자식이 둘이라면 자식들 중 큰 값과 교환한다.
해당 노드가 더이상 교환되지 않을 때까지 3~4번 과정을 반복한다.

    func leftChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index)
    }

    func rightChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index) + 1
    }

    mutating func pop() -> T? {
        guard !tree.isEmpty else { return nil }

        if tree.count == 2 {
            let value = tree[1]
            tree.removeAll()
            return value
        }

        tree.swapAt(1, tree.count - 1)
        let value = tree.removeLast()

        moveDown(from: 1)

        return value
    }

    mutating func moveDown(from index: Int) {
        var parent = index
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            var popped = parent

            if left <= count && tree[left] > tree[popped] {
                popped = left
            }
            if right <= count && tree[right] > tree[popped] {
                popped = right
            }
            if popped == parent {
                return
            }
            tree.swapAt(parent, popped)
            parent = popped
        }
    }

tree의 index가 1부터 시작하기 때문에 앞에 조건 2가지가 붙습니다. 비었을 때 nil 반환, 2개일 때 모든 삭제하고 마지막값 반환하기.

테스트해보자.

var heap = Heap(withData: 10)
heap.insert(50)
heap.insert(20)
heap.insert(100)
print(heap.tree)

heap.pop()
heap.pop()
print(heap.tree)

// [10, 100, 50, 20, 10]
// [10, 20, 10]

잘 나옵니다!

최대힙트리를 구현했지만 최소힙트리를 구현하려면 마이너스로 값을 변환하여 집어넣을 수도 있고 구현한 코드의 부등호를 반대로 바꾸면 됩니다. 반대로 바꿀려면 많이 바꾸어야 하기 때문에 initializer에서 받을 수도 있습니다.

struct Heap<T: Comparable> {
    var tree: [T] = []
    let sort: (T, T) -> Bool
    init(withData data: T, sort: @escaping (T, T) -> Bool) {
        tree.append(data)
        tree.append(data)
        self.sort = sort
    }

  	// ...
}

var heap = Heap(withData: 40, sort: >)

지금까지 구현한 코드

struct Heap<T: Comparable> {
    var tree: [T] = []

    init(withData data: T) {
        tree.append(data)
        tree.append(data)
    }

    var isEmpty: Bool {
        return tree.isEmpty
    }

    var count: Int {
        return tree.isEmpty ? 0 : tree.count - 1
    }

    func top() -> T? {
        return tree.isEmpty ? nil : tree[1]
    }

    mutating func insert(_ data: T) {
        // 비었다면 초기화가 필요합니다.
        if tree.isEmpty {
            tree.append(data)
            tree.append(data)
            return
        }

        // 가장 뒤에 노드를 삽입합니다.
        tree.append(data)

        var newNodeIndex = tree.count - 1
        var parentNodeIndex = newNodeIndex / 2
        while tree[parentNodeIndex] < tree[newNodeIndex] {
            tree.swapAt(parentNodeIndex, newNodeIndex)
            newNodeIndex = parentNodeIndex
            parentNodeIndex = newNodeIndex / 2

            // 현재 노드가 루트노드이면 더이상 비교하지 않습니다.
            if newNodeIndex == 1 { break }
        }
    }

    func leftChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index)
    }

    func rightChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index) + 1
    }

    mutating func pop() -> T? {
        guard !tree.isEmpty else { return nil }

        if tree.count == 2 {
            let value = tree[1]
            tree.removeAll()
            return value
        }

        tree.swapAt(1, tree.count - 1)
        let value = tree.removeLast()
        moveDown(from: 1)

        return value
    }

    mutating func moveDown(from index: Int) {
        var parent = index
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            var popped = parent

            if left <= count && tree[left] > tree[popped] {
                popped = left
            }
            if right <= count && tree[right] > tree[popped] {
                popped = right
            }
            if popped == parent {
                return
            }
            tree.swapAt(parent, popped)
            parent = popped
        }
    }
}

인덱스가 0부터 시작할 때의 Heap의 구현

struct Heap1<T: Comparable> {
    var tree = [T]()
    let sort: (T, T) -> Bool

    init(sort: @escaping (T, T) -> Bool) {
        self.sort = sort
    }

    var isEmpty: Bool {
        return tree.isEmpty
    }

    var count: Int {
        return tree.count
    }

    func peek() -> T? {
        return tree.first
    }

    func leftChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index) + 1
    }

    func rightChildIndex(ofParentAt index: Int) -> Int {
        return (2 * index) + 2
    }

    func parentIndex(ofChildAt index: Int) -> Int {
        return (index - 1) / 2
    }

    mutating func insert(_ element: T) {
        tree.append(element)
        moveUp(from: tree.count - 1)
    }

    mutating func moveUp(from index: Int) {
        var child = index
        var parent = parentIndex(ofChildAt: child)
        while child > 0 && sort(tree[child], tree[parent]) {
            tree.swapAt(child, parent)
            child = parent
            parent = parentIndex(ofChildAt: child)
        }
    }

    mutating func pop() -> T? {
        guard !tree.isEmpty else { return nil }

        if tree.count == 2 {
            let value = tree[1]
            tree.removeAll()
            return value
        }

        tree.swapAt(1, tree.count - 1)
        let value = tree.removeLast()
        moveDown(from: 1)
        return value
    }
  
    mutating func moveDown(from index: Int) {
        var parent = index
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            var candidate = parent

            if left < count && sort(tree[left], tree[candidate]) {
                candidate = left
            }
            if right < count && sort(tree[right], tree[candidate]) {
                candidate = right
            }
            if candidate == parent {
                return
            }
            tree.swapAt(parent, candidate)
            parent = candidate
        }
    }
}

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

TIL_2022:10:10_heap.md

TIL_2022:10:10_heap.md

Today I Learned

Swift로 구현해보기

Files

TIL_2022:10:10_heap.md

Latest commit

History

TIL_2022:10:10_heap.md

File metadata and controls

Today I Learned

Swift로 구현해보기