Heap 자료구조

다익스트라 알고리즘을 공부하다가, 최소 힙에 대한 개념이 필요해서 구현하게 되었다. Swift는 왜 최소 힙 안 주냐~ 그래도 직접 구현하면서 많은 공부를 할 수 있었다.

우선순위 큐

개념

컴퓨터에서도 우선순위 개념이 필요할 때가 있다.
- 네트워키 패킷 중에서 네트워크 관리와 관련된 것들은 일반 패킷보다 운선순위를 가져야한다.
- 운영 시스템에서 시스템 프로세스가 용 프로세스보다 우선순위를 가진다.
- 이러한 이유 때문에 자료구조에서도 우선순위를 지원하는 것이 필요하다.
우선순위 큐(Priority Queue)는 우선순위에 대한 개념을 큐에 도입한 자료구조이다.
- 조금 더 생각해보면, 일반적인 스택이나 큐도 우선순위 큐로 표현할 수 있다.
  - 큐: 데이터 삽입 시간이 빠른 것을 높은 우선순위로 생각한다.
  - 스택: 데이터 삽입 시간이 느린 것을 높은 우선순위로 생각한다.
우선순위 큐는 여러 분야에서 다양하게 이용된다.
- 시뮬레이션, 네트워크 트래픽 제어, 작업 스케줄링, 수치 해석 등
- 배열, 연결리스트 등 여러 방법으로 구현 가능하지만, 힙을 이용했을 때 가장 효율적으로 구현할 수 있다.

구현 방법

배열 사용

정렬되지 않은 배열
- 삽입 O(1) : 기존 요소의 맨 끝에 삽입한다.
- 삭제 O(n) : 모든 요소를 스캔하여 우선순위가 높은 것을 찾고, 남은 요소들을 앞으로 이동시킨다.
정렬된 배열
- 삽입 O(n) : 비교를 통해 삽입 위치를 찾고, 남은 요소들을 이동시켜 삽입시킨다.
- 삭제 O(1) : 맨 뒤에 있는 요소를 삭제한다.

연결리스트 사용

정렬되지 않은 연결리스트
- 삽입 O(1) : 첫번재 노드에 삽입한다.
- 삭제 O(n) : 비교를 통해 제일 우선순위가 높은 것을 찾아 삭제한다.
정렬된 연결리스트
- 삽입 O(n) : 우선순위에 맞는 위치를 찾아 삽입한다. (요소의 이동은 필요 없다)
- 삭제 O(1) : 첫 번째 노드를 삭제한다.

힙의 사용

삽입, 삭제 모두 O(logN)의 성능을 보인다.

힙

서론이 매우 길었다! 힙이 무엇인지 알아보자

개념

여러 개의 값들 중 가장 큰 값이나, 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다.
부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다. (키 값 = 우선순위로 생각하자)
- $Key(A) >= Key(B)$ (A는 B의 부모)
- 위 조건을 만족하는 이진트리를 힙이라고 부른다.
힙은 중복 데이터가 허용된다. (이진트리는 허용되지 않는다)
큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있는 느슨한 정렬 상태를 유지한다. (전체를 정렬할 필요가 없다)
- 같은 레벨 간에는 정렬이 될 필요 없다. 부모와의 관계만 신경쓰면 된다.
힙은 완전 이진트리이기 때문에, 중간에 비어있는 노드가 없다 -> 힙을 저장하는 효과적인 구조는 배열이 된다
- 1번째 인덱스부터 유효한 값을 저장하게 되면 다음과 같은 관계가 성립한다.
  - 왼쪽 자식의 위치 = index * 2
  - 오른쪽 자식의 위치 = index * 2 + 1
  - 부모의 위치 = index / 2

삽입 연산

새로운 노드를 힙 마지막 노드에 삽입한다.
부모와 비교하며 부모보다 자신의 우선순위가 높다면, 부모와 위치를 교환하며 자신의 위치를 탐색한다.
자신이 저장되어야 할 위치를 찾아 저장한다.

삭제 연산

루트 노드를 삭제한다.
힙의 마지막 노드를 루트 노드로 옮긴다.
현재 위치에서 자식 노드들과 위치를 비교하며, 자신의 자리를 찾아간다.

이를 구현할 때, swap을 통해 실제로 값을 구현하는 것이 아니라, 위치를 정확히 찾은 후에 자신을 저장하는 방식으로 구현했다.

구현 (최소 힙)

struct Heap<T: Comparable> {
    var heap = [T]()
    
    func isEmpty() -> Bool {
        heap.count <= 1
    }
    func getParent(_ index: Int) -> T {
        heap[index / 2]
    }
    
    func getLeft(_ index: Int) -> T {
        heap[index * 2]
    }
    
    func getRight(_ index: Int) -> T {
        heap[index * 2 + 1]
    }
    
    mutating func insert(_ data: T) {
        if heap.isEmpty { heap.append(data) } // 0번째 인덱스는 사용하지 않는다. (쓰레기 값)
        heap.append(data)
        var index = heap.count - 1
        while index > 1 {
            let parent = getParent(index)
            guard data < parent else { break }
            heap[index] = parent              // swap을 사용하지 않고 값만 저장한다.
            index = index / 2
        }
        heap[index] = data
    }
    
    mutating func remove() -> T? {
        if isEmpty() { return nil }
        let item = heap[1]
        let last = heap.removeLast()
        let size = heap.count - 1
        
        guard !isEmpty() else { return item }
        var (parent, child) = (1, 2)
        
        while child <= size {
            if child < size && getLeft(parent) > getRight(parent) {
                child += 1 // 오른쪽 자식이 더 작다면, 2n + 1로 child를 설정한다.
            }
            if last <= heap[child] { break } // 이동할 필요가 없다면 반복문을 종료한다.
            heap[parent] = heap[child]
            parent = child
            child *= 2
        }
        heap[parent] = last // 마지막 위치에 있던 노드를 새로운 위치에 저장한다.
        return item // 첫번째 노드를 리턴한다.
    }
}

Previous자료구조 NextClean code

Last updated 1 year ago