자료구조 - Heap (2) 정렬

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

---

Heap sort

힙 자료구조를 이용한 정렬 방법에는 두 가지가 존재한다.

1. 정렬 대상인 데이터들을 힙에 넣었다가 꺼내는 방법
2. 기존의 배열을 heapify를 거쳐 꺼내는 방법

[정렬 대상인 데이터들을 힙에 넣었다가 꺼내는 방법]

1. 정렬해야 할 n개의 요소들로 힙을 초기화한다.
2. 그다음으로 한 번에 하나씩 요소를 힙에서 꺼내 배열의 뒤부터 저장하면 된다.

• 시간 복잡도 : 요소의 개수가 n개이므로 전체적으로 O(nlog2n)의 시간이 걸린다.
• 공간 복잡도 : 추가적인 O(n) 만큼의 공간이 필요하다

// Heap 구현은 https://liam777.tistory.com/37 참고
extension Array where Element: Comparable {
    mutating func sortByInsertToHeap() {
        var maxHeap = Heap<Element>()
        
        // 1
        for element in self {
            maxHeap.insert(element)
        }
        
        // 2
        for i in stride(from: self.count - 1, through: 0, by: -1) {
            if let element = maxHeap.pop() {
                self[i] = element
            }
        }
    }
}

var intArray = [3, 4, 2, 1, 6, 7, 9, 11]
intArray.sortByInsertToHeap()
print(intArray) // [1, 2, 3, 4, 6, 7, 9, 11]

 
[기존의 배열을 heapify를 거쳐 꺼내는 방법]
 
Heapify

• 두 개의 서브트리가 max-heap이라고 가정할 때 root에 추가된 노드를 포함한 전체가 heap을 만족하도록 각 노드들의 위치를 조정하는 과정이다.
• 앞서 살펴본 upheap과 downheap 모두 heapify라고 할 수 있다.

Build Heap

• 임의의 데이터 배열에서 Heap을 구성하는 것이다.
• 직관적으로 이해하기
  • 힙을 구성하는 완전 이진트리는 그 성질에 의해 약 n/2개의 노드는 리프 노드에 존재한다.
  • 따라서 downheap 연산으로 힙을 설계하는 것이 효율적일 것임을 추론할 수 있다.

https://ratsgo.github.io/data structure&algorithm/2017/09/27/heapsort/

 

• 리프 노드보다 한 단계 높은 레벨에서부터 차례대로 heapify(downheap)을 수행
• 한 개 노드를 heapify 하는데 필요한 시간은 O(logn)이고 n/2개 노드에 대해 수행하므로 전체적으로 O(nlogn)이 걸린다?

하지만 조금 더 생각해보자

• 위의 완전 이진트리에서 리프 노드의 레벨을 d라고 하면 레벨이 d인 노드의 수는 n/2이다.
• 그리고 레벨 d-1의 노드 수는 n/4이 된다.

 

• build heap의 시간 복잡도는 수행 대상의 노드가 전체 트리에서 차지하는 높이, 그리고 수행 대상의 노드 수에 비례한다.
• 레벨 d-1인 노드에서의 서브트리는 그 높이가 1(= 리프 노드까지의 앳지 수)이다.
• 마찬가지로 d-2는 2, d-3은 3이 된다.
• 따라서 아래 계산 식에 의해 build heap의 시간 복잡도는 O(n)이 된다.

https://ratsgo.github.io/data structure&algorithm/2017/09/27/heapsort/

 
 
[Swift로 구현한 buildheap]
 
최초 힙 구성 시 배열의 중간부터 시작하면 위에 서술한 이진트리의 성질에 의해 모든 요소 값을 서로 한번씩 비교할 수 있다.

extension Array where Element: Comparable {
    private mutating func buildheap() {
        let mid = self.count - 1
        
        for i in stride(from: mid, through: 0, by: -1) {
            self.downheap(from: i, count: self.count)
        }
    }

    private mutating func downheap(from index: Int, count: Int) {
        guard index < count else { return }
        
        var largestIndex = index
        var leftIndex = self.leftIndexWhenHeap(from: index)
        var rightIndex = self.rightIndexWhenHeap(from: index)
        
        if leftIndex < count && self[leftIndex] > self[largestIndex] {
            largestIndex = leftIndex
        }
        
        if rightIndex < count && self[rightIndex] > self[largestIndex] {
            largestIndex = rightIndex
        }
        
        if largestIndex != index {
            self.swapAt(largestIndex, index)
            self.downheap(from: largestIndex, count: count)
        }
    }
    
    private func leftIndexWhenHeap(from index: Int) -> Int {
        return 2 * index
    }
    
    private func rightIndexWhenHeap(from index: Int) -> Int {
        return 2 * index + 1
    }
}

 
Heap Sort

1. Build heap 단계
2. 한번 힙이 구성되면 최상위 노드를 가장 마지막으로 보내고 마지막 인덱스를 제외하고 heapify를 다시 수행

[Swift로 구현한 heapSortByHeapify]

extension Array where Element: Comparable {
    
    mutating func sortByHeapify() {
        // 1
        self.buildheap()
        
        // 2
        for i in stride(from: self.count - 1, through: 0, by: -1) {
            self.swapAt(0, i)
            self.downheap(from: 0, count: i)
        }
    }
    
    private mutating func buildheap() {
        let mid = self.count - 1
        
        for i in stride(from: mid, through: 0, by: -1) {
            self.downheap(from: i, count: self.count)
        }
    }

    ...
}

var intArray = [3, 4, 2, 1, 6, 7, 9, 11]
intArray.sortByHeapify()
print(intArray) // [1, 2, 3, 4, 6, 7, 9, 11]

 

• 시간 복잡도 : O(n) + O(nlogn) = O(nlogn)
  • 최초로 최대 힙을 만드는 시간 복잡도 (build heap) : O(n)
  • 힙이 구성된 상태에서 각 노드에 대해 heapify를 수행 : O(nlogn) 
• 공간 복잡도 : 추가적인 공간 필요 없음

 
 
전체 구현 코드

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
    }
}

extension Array where Element: Comparable {
    mutating func sortByInsertToHeap() {
        var maxHeap = Heap<Element>()
        
        // 1
        for element in self {
            maxHeap.insert(element)
        }
        
        // 2
        for i in stride(from: self.count - 1, through: 0, by: -1) {
            if let element = maxHeap.pop() {
                self[i] = element
            }
        }
    }
}

extension Array where Element: Comparable {
    
    mutating func sortByHeapify() {
        // 1
        self.buildheap()
        
        // 2
        for i in stride(from: self.count - 1, through: 0, by: -1) {
            self.swapAt(0, i)
            self.downheap(from: 0, count: i)
        }
    }
    
    private mutating func buildheap() {
        let mid = self.count - 1
        
        for i in stride(from: mid, through: 0, by: -1) {
            self.downheap(from: i, count: self.count)
        }
    }

    private mutating func downheap(from index: Int, count: Int) {
        guard index < count else { return }
        
        var largestIndex = index
        var leftIndex = self.leftIndexWhenHeap(from: index)
        var rightIndex = self.rightIndexWhenHeap(from: index)
        
        if leftIndex < count && self[leftIndex] > self[largestIndex] {
            largestIndex = leftIndex
        }
        
        if rightIndex < count && self[rightIndex] > self[largestIndex] {
            largestIndex = rightIndex
        }
        
        if largestIndex != index {
            self.swapAt(largestIndex, index)
            self.downheap(from: largestIndex, count: count)
        }
    }
    
    private func leftIndexWhenHeap(from index: Int) -> Int {
        return 2 * index
    }
    
    private func rightIndexWhenHeap(from index: Int) -> Int {
        return 2 * index + 1
    }
}

 

---

 

참고

https://ratsgo.github.io/data%20structure&algorithm/2017/09/27/heapsort/

힙 정렬(Heap Sort) · ratsgo's blog