[Algorithm] 힙 정렬(HeapSort)이란? (feat.Swift)

안녕하세요 Foma 💻 입니다!

 

저번 시간에 힙이란 자료구조에 대해서 알아보았는데요. (혹시라도 안보신 분은 여기 에서 보고 와주세요!)

 

오늘은 힙을 이용해서 정렬을 하는 힙소트에 대해서 알아보려고 합니다!

바로 시작할게요~

---

힙 정렬((HeapSort)이란? 🧐

 

힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. - 위키 백과 -

 

즉, 힙을 이용해서 정렬을 하는 방식이에요.

---

힙 정렬 과정 🔨

 

힙 정렬 과정은 힙에서 삭제를 구현할 때와 똑같아요.

 

삭제과정이 아래와 같은데요.

 

 

 

 

모든 노드를 삭제하고 배열에 차례로 쌓게되면 어떻게 될까요?

 

최대힙이라면 가장 큰 숫자가 차례로 쌓이게 될거고 최소힙이라면 가장 작은 숫자가 차례로 쌓이게 되겠죠?

 

즉, 오름차순 혹은 내림차순으로 정렬할 수 있게되는 것이죠.

 

아래는 힙정렬을 해나가는 과정이에요.

 

출처:위키백과

---

시간복잡도

 

힙 정렬의 시간복잡도는 N개의 노드를 최대 logN번 Heapify하는 과정을 거치기 때문에 O(nlogn)입니다.

---

코드 구현

 

먼저 저번 시간에 만들어놓았던 MaxHeap을 가져오겠습니다.

 

 

코드로 구현하는 것은 간단합니다.

 

우선 주어진 배열을 힙으로 만들어주고, 배열에 있는 모든 숫자를 없애줍니다.

 

그리곤 heap에 있는 최댓값을 차례로 배열에 넣어주면서 삭제하는 과정을 거치면 정렬이 완성됩니다.

 

var numbers:[Int] = [4,1,7,5,3,2,6]

extension Array where Element == Int{
    mutating func sortByHeap(descending:Bool) -> [Element] {
        var heap = MaxHeap(nodes: self)
        self.removeAll()
        for _ in heap.nodes {
            if let max = heap.nodes.first {
                if descending {
                    self.append(max)
                }else {
                    self.insert(max, at: 0)
                }
            }
            heap.remove()
        }
        return self
    }
}

numbers.sortByHeap(descending: false)//[1,2,3,4,5,6,7]
numbers.sortByHeap(descending: true)//[7,6,5,4,3,2,1]