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

안녕하세요 Foma 💻 입니다!

 

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

 

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

바로 시작할게요~

---

힙 정렬((HeapSort)이란? 🧐

 

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

 

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

---

힙 정렬 과정 🔨

 

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

 

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

 

 

 

 

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

 

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

 

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

 

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

 

출처:위키백과

---

시간복잡도

 

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

---

코드 구현

 

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

 

	import Foundation
	struct MaxHeap {
	var nodes:[Int] = []
	init(nodes:[Int]) {
	nodes.forEach {
	insert($0)
	}
	}
	private func getLeftChildIndex(_ parentIndex: Int) -> Int {
	return 2 * parentIndex + 1
	}
	private func getRightChildIndex(_ parentIndex: Int) -> Int {
	return 2 * parentIndex + 2
	}
	private func getParentIndex(_ childIndex: Int) -> Int {
	return (childIndex - 1) / 2
	}
	private func hasLeftChild(_ index: Int) -> Bool {
	return getLeftChildIndex(index) < nodes.count
	}
	private func hasRightChild(_ index: Int) -> Bool {
	return getRightChildIndex(index) < nodes.count
	}
	private func hasParent(_ index: Int) -> Bool {
	return getParentIndex(index) >= 0
	}
	mutating private func heapifyUp() {
	var index = nodes.count - 1
	while hasParent(index) && nodes[getParentIndex(index)] < nodes[index] {
	nodes.swapAt(getParentIndex(index),index)
	index = getParentIndex(index)
	}
	}
	mutating func insert(_ node:Int) {
	nodes.append(node)
	heapifyUp()
	}
	mutating private func heapifyDown() {
	var index = 0
	while hasLeftChild(index) {
	let leftIndex:Int = getLeftChildIndex(index)
	let rightIndex:Int = getRightChildIndex(index)
	var biggerChildIndex = leftIndex
	if hasRightChild(index) && nodes[leftIndex] < nodes[rightIndex] {
	biggerChildIndex = rightIndex
	}
	if nodes[index] > nodes[biggerChildIndex] {
	break
	} else {
	nodes.swapAt(index, biggerChildIndex)
	}
	index = biggerChildIndex
	}
	}
	mutating func remove() {
	if nodes.isEmpty {
	return
	}
	nodes.swapAt(0, nodes.count - 1)
	nodes.removeLast()
	heapifyDown()
	}
	}

view raw MaxHeap.swift hosted with ❤ by GitHub

 

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

 

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

 

그리곤 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]