자료구조 - Heap (1) 기본

C언어로 쉽게 풀어쓴 자료구조를 읽으며 정리

Priorty Queue

우선순위를 가진 항목들을 저장하는 큐
FIFO 순서가 아니라 우선순위가 높은 데이터가 먼저 나가게 됨

응용분야

시뮬레이션 시스템 (여기서의 우선순위는 대개 사건의 시각)
운영 체제에서의 작업 스케줄링
네트워크 트래픽 제어

시간복잡도

우선순위 큐는 배열로 구현할 수도 있고 연결 리스트로 구현할 수도 있지만

시간 복잡도 면에서 가장 좋은 방법은 힙(Heap)으로 구현하는 것이다.

표현 방법	삽입	삭제
배열 (정렬)	O(1)	O(n)
배열 (비정렬)	O(n)	O(1)
연결 리스트 (정렬)	O(1)	O(n)
연결 리스트 (비정렬)	O(n)	O(1)
트리(heap) (부분정렬)	O(logn)	O(logn)

Heap

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조
힙은 트리 중에서도 배열에 기반한 Complete Binary Tree
느슨한 정렬 상태 : 큰 값이 상위 레벨이 있고, 작은 값이 하위 레벨에 있다 정도
- 히프의 목적은 삭제 연산시 가장 큰 값(또는 작은 값)을 찾아내기만 하면 되는 것이기 때문

Max Heap

각 노드의 값이 해당 자식 노드의 값보다 크거나 같은 Complete Binary Tree
루트 노드에 있는 값이 가장 크기 때문에, 최댓 값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.
n개의 노드를 갖고 있는 힙의 높이는 ceil(log2(n+1)) 이다.

Heap의 구조를 계속 유지하기 위해서는 제거된 루트 노드를 대체할 다른 노드가 필요하다. 여기서 힙은 맨 마지막 노드를 루트 노드로 대체시킨 후, 다시 heapify 과정을 거쳐 heap 구조를 유지한다. 이런 경우에는 결국 O(logn)의 시간복잡도로 최댓 값 또는 최솟 값에 접근할 수 있게 된다.

Min Heap

각 노드의 값이 해당 자식의 값보다 작거나 같은 Complete Binary Tree

구현

complete binary tree이기 때문에 배열을 사용하여 효율적으로 관리할 수 있다.
- random access가 가능하다.
배열에 트리의 값들을 넣어줄 때 0번째는 건너뛰고 1번 인덱스부터 루트노드가 시작된다.
- 이는 노드의 고유번호 값과 배열의 인덱스를 일치시켜 혼동을 줄이기 위함이다.
- 루트가 1번에서 시작해야 i번째 노드에 대하여 부모 노드는 i/2, 왼쪽 노드는 2i, 오른쪽 노드는 2i+1의 인덱스를 가짐

import Foundation

struct Heap<Element: Comparable> {
    private var _heap: [Element?] = []
    
    private let rootIndex: Int = 1
    private var lastIndex: Int { self._heap.count - 1 }
    
    var hasElement: Bool { self.count != 0 }
    var isEmpty: Bool { self.count == 0 }
    var count: Int { max(0, self._heap.count - 1) }
    
    var hasElement: Bool { !self.isEmpty }
    var isEmpty: Bool { self.lastIndex < self.rootIndex }
        
    private func parentIndex(of index: Int) -> Int {
        return index / 2
    }
    
    private func leftChildIndex(of index: Int) -> Int {
        return index * 2
    }
    
    private func rightChildIndex(of index: Int) -> Int {
        return index * 2 + 1
    }
}

Swift로 내부적으로 배열의 첫번째 인덱스에 nil 값을 저장하도록 구현해봄

힙의 삽입 연산 (upheap)

힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입
삽입 후에 새로운 노드를 힙의 성질을 만족시킬 때 까지 부모 노드와 교환한다.
- 최대 힙에서 현재 노드의 키가 부모 노드의 키보다 작거나 같으면 종료
- 힙의 높이가 ceil(O(log2(n+1))이므로 upheap 연산은 O(logn)의 시간복잡도를 갖는다.

struct Heap<Element: Comparable> {
    ...
    mutating func insert(_ element: Element) {
        guard self.hasElement else {
            self._heap = [nil, element]
            return
        }
        
        // Swift는 동적 배열이기 때문에 최악의 경우 시간 복잡도는 O(n)
        // 항상 O(logn)의 성능을 원한다면 배열의 크기를 제한하면 되겠다.
        self._heap.append(nil)
        
        self.upheap(from: self.lastIndex, target: element)
    }
    
    private mutating func upheap(from index: Int, target: Element) {
        var parentIndex = self.parentIndex(of: index)
        
        guard index != self.rootIndex else {
            self._heap[index] = target
            return
        }
        
        guard let parent = self._heap[parentIndex],
              target > parent else {
            self._heap[index] = target
            return
        }
        
        self._heap[index] = self._heap[parentIndex]
        self.upheap(from: parentIndex, target: target)
    }
    ...    
}

Swift의 append는 최악의 경우 O(n)의 시간복잡도를 가짐. 시간 복잡도를 더욱 개선할 목적이라면 배열의 크기를 제한하면 되겠다.
반복문 대신 재귀 호출로 가독성을 높여봄
swap을 진행하는 대신 부모 노드만 끌어내린 후 삽입할 위치가 정해지면 해당 노드를 위치 시켜 연산 횟수를 개선

힙의 삭제 연산 (downheap)

루트 노드를 삭제한다.
마지막 노드를 루트 노드로 이동한다.
루트에서 단말 노드까지의 경로에 있는 노드들을 교환하여 히프의 성질을 만족시킨다. 최대 힙의 경우 현재 위치에서 자식 노드 중에서 큰 값과 교환을 진행한다.
- 가장 아래 레벨까지 내려가야 하므로 트리의 높이 만큼의 시간이 필요하다.
- 따라서 시간 복잡도는 O(logn)

import Foundation

struct Heap<Element: Comparable> {
    ...
    mutating func pop() -> Element? {
        guard self.hasElement else { return nil }
        
        let result = self._heap[self.rootIndex]
        
        if self.count == 1 {
            self._heap = []
            return result
        }
        
        self._heap[self.rootIndex] = self._heap.removeLast()
        
        guard let target = self._heap[self.rootIndex] else {
            self._heap = []
            return result
        }
        
        self.downHeap(from: self.rootIndex, target: target)
        
        return result
    }
    
    mutating func downHeap(from index: Int, target: Element) {
        guard let (childIndex, child) = self.findLargerChild(from: index) else {
            self._heap[index] = target
            return
        }
        
        guard target < child else {
            self._heap[index] = target
            return
        }
        
        self._heap[index] = child
        
        self.downHeap(from: childIndex, target: target)
    }
    
    private func findLargerChild(from index: Int) -> (Int, Element)? {
        let leftChildIndex = self.leftChildIndex(of: index)
        let rightChildIndex = self.rightChildIndex(of: index)
        
        guard leftChildIndex <= self.lastIndex,
              let left = self._heap[leftChildIndex] else {
            return nil
        }
        
        if rightChildIndex <= self.lastIndex,
           let right = self._heap[rightChildIndex],
           left < right {
            return (rightChildIndex, right)
        } else {
            return (leftChildIndex, left)
        }
    }
    ...
}

insert 구현과 비슷한 컨셉

Heap Swift 구현 전체 코드

import Foundation

struct Heap<Element: Comparable> {
    private var _heap: [Element?] = []
    
    private let rootIndex: Int = 1
    private var lastIndex: Int { self._heap.count - 1 }
    
    var hasElement: Bool { self.count != 0 }
    var isEmpty: Bool { self.count == 0 }
    var count: Int { max(0, self._heap.count - 1) }
    
    mutating func insert(_ element: Element) {
        guard self.hasElement else {
            self._heap = [nil, element]
            return
        }
        
        // Swift는 동적 배열이기 때문에 최악의 경우 시간 복잡도는 O(n)
        // 항상 O(logn)의 성능을 원한다면 배열의 크기를 제한하면 되겠다.
        self._heap.append(nil)
        
        self.upheap(from: self.lastIndex, target: element)
    }
    
    private mutating func upheap(from index: Int, target: Element) {
        var parentIndex = self.parentIndex(of: index)
        
        guard index != self.rootIndex else {
            self._heap[index] = target
            return
        }
        
        guard let parent = self._heap[parentIndex],
              target > parent else {
            self._heap[index] = target
            return
        }
        
        self._heap[index] = self._heap[parentIndex]
        self.upheap(from: parentIndex, target: target)
    }
    
    mutating func pop() -> Element? {
        guard self.hasElement else { return nil }
        
        let result = self._heap[self.rootIndex]
        
        if self.count == 1 {
            self._heap = []
            return result
        }
        
        self._heap[self.rootIndex] = self._heap.removeLast()
        
        guard let target = self._heap[self.rootIndex] else {
            self._heap = []
            return result
        }
        
        self.downHeap(from: self.rootIndex, target: target)
        
        return result
    }
    
    mutating func downHeap(from index: Int, target: Element) {
        guard let (childIndex, child) = self.findLargerChild(from: index) else {
            self._heap[index] = target
            return
        }
        
        guard target < child else {
            self._heap[index] = target
            return
        }
        
        self._heap[index] = child
        
        self.downHeap(from: childIndex, target: target)
    }
    
    private func findLargerChild(from index: Int) -> (Int, Element)? {
        let leftChildIndex = self.leftChildIndex(of: index)
        let rightChildIndex = self.rightChildIndex(of: index)
        
        guard leftChildIndex <= self.lastIndex,
              let left = self._heap[leftChildIndex] else {
            return nil
        }
        
        if rightChildIndex <= self.lastIndex,
           let right = self._heap[rightChildIndex],
           left < right {
            return (rightChildIndex, right)
        } else {
            return (leftChildIndex, left)
        }
    }
    
    private func parentIndex(of index: Int) -> Int {
        return index / 2
    }
    
    private func leftChildIndex(of index: Int) -> Int {
        return index * 2
    }
    
    private func rightChildIndex(of index: Int) -> Int {
        return index * 2 + 1
    }
}

'CS > 자료구조' 카테고리의 다른 글

자료구조 - Heap (2) 정렬 (2)	2024.09.16
자료구조 - 트리 (0)	2024.08.24
자료구조 - 스택, 큐, 덱 (0)	2024.08.17
자료 구조 - 배열, 연결 리스트 (1)	2024.08.14
자료 구조 - 순환 (Recursion) (0)	2024.08.12

리암

자료구조 - Heap (1) 기본

Priorty Queue

Heap

'CS > 자료구조' 카테고리의 다른 글

티스토리툴바

자료구조 - Heap (1) 기본

Priorty Queue

Heap

'CS > 자료구조' 카테고리의 다른 글

'CS/자료구조' Related Articles

티스토리툴바