[Data Structure / Algorithms] Heap Sort

주제: 힙 정렬이란

---

힙 정렬

• 힙 정렬이란 힙을 이용해 오름차순으로 정렬하는 비교 기반 알고리즘입니다.
• 힙 정렬은 힙이 부분적으로 정렬된 이진 트리임을 활용합니다.

  • 최대 힙에서, 모든 부모 노드는 자식 노드보다 큽니다.
  • 최소 힙에서, 모든 부모 노드는 자식 노드보다 작습니다.

• 힙 정렬의 최선, 최악 및 평균 시간복잡도는 모두 O(n log n)이며, 이러한 성능의 균일성은 전체 목록을 한 번 훑고, 요소를 교환할 때마다 O(log n) 작업인 sift down을 수행하기 때문입니다.

구현

Heap Sift Down 함수 추가

• Heap에 있는 siftDown 함수를 수정해야 합니다. 이때 upTo 매개변수를 추가해서 siftDown 메서드를 설정해야합니다. upTo 매개변수는 배열의 정렬되지 않은 부분만을 대상으로 shiftDown 연산을 수행하도록 제한하는데 사용됩니다.
• 정렬된 부분과 미정렬 부분의 구분

  upTo 매개변수는 shiftDown이 수행되는 배열의 범위를 제한합니다. 즉, upTo 인덱스 이전까지의 배열 부분만 shiftDown 대상이 됩니다.

    private mutating func siftDown(from index: Int, upTo: Int) {
        var parent = index
        
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            var candidate = parent
            if left < upTo && sort(elements[left], elements[candidate]) {
                candidate = left
            }
            
            if right < upTo && sort(elements[right], elements[candidate]) {
                candidate = right
            }
            if candidate == parent {
                return
            }
            
            elements.swapAt(parent, candidate)
            parent = candidate
        }
    }

정렬 구현

extension Heap { 
	func sorted() -> [Element] { 
		var heap = Heap(sort: sort, elements: elements)
		for index in heap.elements.indices.reversed() { 
			heap.elements.swapAt(0, index)
			heap.siftDown(from: 0, upTo: index)
		}
		return heap.elements
	}
}

var heapTest = Heap(sort: <, elements: [1,2,3,4,3,1,32,45,32])

print(heapTest)

var sortedHeap = heapTest.sorted()
sortedHeap.reverse()

print(sortedHeap)

Heap<Int>(elements: [1, 2, 1, 4, 3, 3, 32, 45, 32], sort: (Function))
[1, 1, 2, 3, 3, 4, 32, 32, 45]

출처(참고문헌)

• https://www.kodeco.com/books/data-structures-algorithms-in-swift/v4.0/chapters/32-heapsort