Chapter 33: Heap Sort Challenges

Challenge 1: Add heap sort to Array

배열(Array)에 heapSort() 메서드를 추가한다. 이 메서드는 배열(Array)을 오름차순(ascending)으로 정렬한다.

 

Solution

배열(Array)에 힙 정렬(heap sort)를 추가하려면, Array의 요소가 Comparable을 구현해야 한다. 다른 부분은 이전에 구현한 힙(heap)과 매우 유사하다.

extension Array where Element: Comparable {
    func leftChildIndex(ofParentAt index: Int) -> Int {
        (2 * index) + 1
    }
    
    func rightChildIndex(ofParentAt index: Int) -> Int {
        (2 * index) + 2
    }
    
    mutating func siftDown(from index: Int, upTo size: Int) {
        var parent = index
        
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            var candidate = parent
            
            if (left < size) && (self[left] > self[candidate]) {
                candidate = left
            }
            
            if (right < size) && (self[right] > self[candidate]) {
                candidate = right
            }
            
            if candidate == parent {
                return
            }
            
            swapAt(parent, candidate)
            parent = candidate
        }
    }
    
    mutating func heapSort() {
        // Build Heap
        if !isEmpty {
            for i in stride(from: count / 2 - 1, through: 0, by: -1) {
                siftDown(from: i, upTo: count)
            }
        }
        
        // Perform Heap Sort.
        for index in indices.reversed() {
            swapAt(0, index)
            siftDown(from: 0, upTo: index)
        }
    }
}

---

Challenge 2: Theory

힙 정렬(heap sort)을 오름차순(ascending)으로 구현할 때, 다음 배열(Array) 중 비교 횟수가 더 적은 배열(Array)은 어떤 것인지 알아본다.

• [1,2,3,4,5]
• [5,4,3,2,1]

 

Solution

힙 정렬(heap sort)을 사용하여 요소(element)를 오름차순(ascending order)으로 정렬할 때에는 최대 힙(max heap)을 사용한다. 따라서 살펴봐야 할 것은 최대 힙(max heap)을 구성할 때 발생하는 비교 횟수이다. [5, 4, 3, 2, 1]은 이미 최대 힙(max heap)이라 교환(swap)이 없기 때문에 비교 횟수가 더 적다. 최대 힙(max heap)을 구성할 때 부모 노드(parent node)만 확인한다. [5, 4, 3, 2, 1]는 두 개의 부모 노드(parent node)가 있으며 2번의 비교가 있다.

 

반면, [1, 2, 3, 4, 5]는 비교 횟수가 더 많다. 두 개의 부모 노드(parent node)가 있지만, 3번의 비교를 해야 한다.

---

Challenge 3: Descending order

지금까지 오름차순(ascending order)로 힙 정렬(heap sort)을 구현했다. 내림차순(descending order)으로 힙 정렬(heap sort)을 구현한다.

 

Solution

간단하게 최대 힙(max heap) 대신 최소 힙(min heap)을 사용하면된다.

let heap = Heap(sort: <, elements: [6, 12, 2, 26, 8, 18, 21, 9, 5])
print(heap.sorted())