안녕하세요 후르륵짭짭 입니다.
이번에는 처음으로 알고리즘 이론을 가져와 봤습니다.
모두 자료구조인 Heap에 대해서 어느정도 알고 있을 거라 생각합니다.
우선순위 큐라 불리는 Heap은 최대값 또는 최소값이 항상 루트 값에 위치 해서 빠른 시간안에 최대 값을 찾아주는 알고리즘 입니다.
그 값의 최대값? 최소값 찾는 것은 그냥 배열의 min() / max() 쓰면 되지 않냐고 생각하시는 분들 있을 수도 있습니다.
하지만 Apple Document에서는 O(n)시간을 가지게 됩니다
developer.apple.com/documentation/swift/array/1688806-max
Apple Developer Documentation
developer.apple.com
그러나 Heap을 쓰면 O(1)시간에 답 구하게 되고 O(logN)시간에 정렬을 마치게 됩니다.
그럼 지금 부터 Heap 알고리즘 구현에 대해서 알아보도록 하겠습니다.
** Heap이란 **
Heap은 위에서 설명 한 것 처럼 최대값과 최소값을 반환해주는 거라 생각하면 됩니다.
예를 들어
[ 단순 감기 환자 , 칼에 찔린 환자 , 손가락 골절 환자, 검강검진 받으로 온 환자 ]
이렇게 있다고 한다면 응급환자는 상식적으로
칼에 찔린 환자 -> 손가락 골절 환자 -> 단순 감기 환자 -> 검강검진 환자
이렇게 해줘야합니다.
이렇게 우선순위를 배푸해서 정렬해주는 것이 Heap입니다.
참 쉽죠???
** Heap 구현 **
Heap에 구현 방법에 대해서 설명 하도록 하겠습니다.
Swift에서는 C++ 이나 JAVA, Python 처럼 Heap 알고리즘을 제공하지 않습니다.
따라서 직접 구현해줘야하는데요....
이번 기회에 공부해보도록 합시다.
struct Heapify<T> {
var element : [T] = []
var isEmpty : Bool {return element.isEmpty}
var size : Int {return element.count}
var isOrdered : (T,T) -> Bool
}일단 이렇게 구조체를 만들어 줍니다.
그리고 어떤 값이던지 Heap 정렬을 해줘야하니 <제너릭>을 받아 옵니다.
그리고 아래 처럼 기본적인 셋팅을 해줍니다.
element - 정렬할 배열
isEmpty - 비었나요?
size - 힙의 크기
isOrdered - 정렬 방식
여기서 isOrdered에 대해서 보도록 하겠습니다.
isOrdered는 두개의 변수를 받는 클로저로 되어 있습니다.
developer.apple.com/documentation/swift/int/2964495
Apple Developer Documentation
developer.apple.com
애플 공식 문서를 본다면 <은 lhs 와 rhs 로 되어 있습니다.
Returns a Boolean value indicating whether the value of the first argument is less than that of the second argument.
그리고 lhs가 rhs 보다 작을 때 참값을 반환하도록 되어 있습니다.
즉, 우리는 isOrdered에 비교해줄 변수 LeftHandSide 와 RightHandSide 두개를 받을 것 입니다.
위의 내용이 이해가 됐다면 아래 코드에 하나가 추가 된 것도 이해가 될 것 입니다.
struct Heapify<T> {
var element : [T] = []
var isEmpty : Bool {return element.isEmpty}
var size : Int {return element.count}
var isOrdered : (T,T) -> Bool
public init(sort : @escaping (T,T) -> Bool){
self.isOrdered = sort
}
}저 sort에 이제 "<" 또는 ">" 이 들어가게 되는 겁니다.
< 일 경우에는 leftHandSide 가 rightHandSide 보다 작을 때로 정렬해주게 됩니다. (올림차순)
(참고로 @escaping이 들어간 것은 isOrdered가 외부 클로저 이기 때문입니다. 외부 클로저에 내부 클로저를 대입 해줄 때는 저렇게 @escaping을 해줘야합니다.)
- 기본적인 노드 탐색 연산 -
private func getParent(_ index : Int) -> Int{
return (index - 1) / 2
}
private func getRightChild(_ index : Int) -> Int{
return (index * 2) + 2
}
private func getLeftChild(_ index : Int) -> Int{
return (index * 2) + 1
}위의 코드는 현재 노드 위치로 부터 부모 노드 탐색과 오른쪽 자식 위치 / 왼쪽 자식을 찾아주는 함수 입니다.
이해가 안된다면 index를 현재 노드라고 생각하고 계산을 해보면 이해가 될 것 입니다.
- 힙 구성하기 -
mutating func buildHeap(inputArray : [T]){
element = inputArray
for i in stride(from: element.count / 2 - 1, to: -1, by: -1){
heapifyDown(i)
}
}예전에 stride를 다룬 적이 있는데요.
(그냥 반복문이라 생각하면 됩니다. 그런데 여기서 to 이전 까지 니깐 to는 포함 안된다는 거 주의 입니다 ㅎㅎ)
여기서 element.count / 2 - 1 가 된 것은. heap을 구성 할때, 자식과 현재 노드의 값을 변동 해줄 때, leaf 노드는 탐색할 필요가 없기 때문입니다.
언제나 Leaf 노드 위의 부모 노드 까지만 탐색하기 위해서 그런 겁니다.
예를 들어 노드가 5개라 한다면 2 3 4 번 노드는 Leaf 노드 이기 때문에 자식을 가진 0과 1번에서만 힙정렬을 해주면 됩니다.
mutating func heapifyDown(_ index : Int){
let leftIndex = getLeftChild(index)
let rightIndex = getRightChild(index)
if leftIndex < element.count && isOrdered(element[leftIndex] , element[index]) {
if rightIndex < element.count && isOrdered(element[rightIndex] , element[leftIndex]){
// print("right Swap : \(index) \(rightIndex)")
element.swapAt(index, rightIndex)
heapifyDown(rightIndex)
}
else{
// print("left Swap : \(index) \(leftIndex)")
element.swapAt(index, leftIndex)
heapifyDown(leftIndex)
}
}
}이게 정말 메인 코드라 할 수 있습니다.
leftIndex에 현재 노드의 왼쪽 자식 노드 위치가 들어갑니다
rightIndex에 현재 노드의 오른쪽 자식 노드 위치가 들어갑니다.
그리고 아래 그림 처럼 작동하게 됩니다.
현재는 위치인 맨 루트 노드의 값과 왼쪽 자식 값과 비교합니다. (MAX 힙이라고 가정 합니다)
if leftIndex < element.count && isOrdered(element[leftIndex] , element[index]) {}그런데 8과 5 중에 왼쪽 자식이 더 크니 통과 합니다.
그리고 왼쪽 자식과 오른쪽 자식을 비교 합니다.
그런데 오른쪽 자식의 값이 왼쪽 보다 크다면 최종적으로 오른쪽 자식 과 루트 값을 위치 변경 시켜줍니다.
if rightIndex < element.count && isOrdered(element[rightIndex] , element[leftIndex]){그러면 Index가 오른쪽으로 이동하게 되고 최종적으로 아래와 같이 현성 될 것 입니다.
만약에 왼쪽이 오른쪽 보다 더욱 컷으로 두번 째 반복문을 통과 하지 않았을 겁니다 ㅎㅎㅎㅎ
_ 노드 삭제하기 -
public mutating func remove() -> T?{
if self.isEmpty {return nil}
let rootItem = element[0]
element.swapAt(0, element.count - 1)
element.removeLast()
heapifyDown(0)
return rootItem
}노드 삭제 행위는 루트 노드 값을 반환 해주는 일 입니다.
따라서 새로운 변수 rootItem에 루트 값을 대입 받고 이 값을 나중에 반환하게 됩니다.
위의 그림을 보면 저 코드가 이해가 될 것 입니다.
- 노드 추가 하기 -
public mutating func insert(item : T){
element.append(item)
heapifyUp(element.count - 1)
}일단 이 코드 부터 보도록 하겠습니다.
element는 배열인데, 그 배열에 새로운 아이템을 추가 해줍니다.
그리고 위로 올라가는 heap 정렬을 하도록 합니다.
mutating func heapifyUp(_ index : Int){
let parentIndex = getParent(index)
if parentIndex >= 0 && isOrdered(element[index], element[parentIndex]){
element.swapAt(parentIndex, index)
heapifyUp(parentIndex)
}
}그럼 이렇게 isOrdered를 해줘서 현재 노드의 값이 부모 노드 보다 크다면 서로 바꿔주고
다시 위로 올라가는 heap 정렬을 재귀 적으로 해줍니다.
지금 까지 Heap 정렬에 대해 공부 해봤는데요!!!
이제 사용 방법을 보도록 하겠습니다.
** 사용 방법 **
let array = [12,3,6,15,45,1,2]
var heap = Heapify<Int>(sort: <)
heap.buildHeap(inputArray: array)처음에 배열을 줍니다.
그리고 heap 구조체를 정렬방식과 함께 생성해주고
buildHeap 메소드를 통해서 Heap을 구성 해줍니다.
print(heap.element)
//결과
[1, 3, 2, 15, 45, 6, 12]그러면 위에 처럼 힙 정렬이 된 것을 확인 할 수 있습니다.
heap.insert(item: 0)
print(heap.element)
//결과
[0, 1, 2, 3, 45, 6, 12, 15]마지막으로 노드를 반환 해주면 아래 처럼 잘 나오는 것을 확인 할 수 있습니다.
while !heap.isEmpty{
print(heap.remove() ?? "없음")
}
//결과
0
1
2
3
6
12
15
45
그리고 이러한 것도 가능 합니다.
var test = Heapify<(a : Int, b :Int)>.init { (element1, element2) -> Bool in
if element1.a == element2.a{
return element1.b < element2.b
}
return element1.a < element2.a
}
let testArray : [(a: Int , b: Int)] = [(1,2),(2,3),(3,4),(1,3),(2,4),(3,5)]
test.buildHeap(inputArray: testArray)
print(test.element)
//결과
[(a: 1, b: 2), (a: 1, b: 3), (a: 3, b: 4), (a: 2, b: 3), (a: 2, b: 4), (a: 3, b: 5)]
** 전체 코드 **
struct Heapify<T> {
var element : [T] = []
var isEmpty : Bool {return element.isEmpty}
var size : Int {return element.count}
var isOrdered : (T,T) -> Bool
public init(sort : @escaping (T,T) -> Bool){
self.isOrdered = sort
}
private func getParent(_ index : Int) -> Int{
return (index - 1) / 2
}
private func getRightChild(_ index : Int) -> Int{
return (index * 2) + 2
}
private func getLeftChild(_ index : Int) -> Int{
return (index * 2) + 1
}
mutating func heapifyDown(_ index : Int){
let leftIndex = getLeftChild(index)
let rightIndex = getRightChild(index)
if leftIndex < element.count && isOrdered(element[leftIndex] , element[index]) {
if rightIndex < element.count && isOrdered(element[rightIndex] , element[leftIndex]){
// print("right Swap : \(index) \(rightIndex)")
element.swapAt(index, rightIndex)
heapifyDown(rightIndex)
}
else{
// print("left Swap : \(index) \(leftIndex)")
element.swapAt(index, leftIndex)
heapifyDown(leftIndex)
}
}
}
mutating func buildHeap(inputArray : [T]){
element = inputArray
for i in stride(from: element.count / 2 - 1, to: -1, by: -1){
heapifyDown(i)
}
}
mutating func heapifyUp(_ index : Int){
let parentIndex = getParent(index)
if parentIndex >= 0 && isOrdered(element[index], element[parentIndex]){
element.swapAt(parentIndex, index)
heapifyUp(parentIndex)
}
}
public mutating func insert(item : T){
element.append(item)
heapifyUp(element.count - 1)
}
public mutating func remove() -> T?{
if self.isEmpty {return nil}
let rootItem = element[0]
element.swapAt(0, element.count - 1)
element.removeLast()
heapifyDown(0)
return rootItem
}
}
'Xcode > Swift - PlayGround' 카테고리의 다른 글
| PlayGround ) Design Pattern (MVC) (0) | 2020.10.02 |
|---|---|
| PlayGround ) Viewcontroller Life Cycle 이란?? (0) | 2020.09.30 |
| PlayGround) Auto Reference Counting(ARC) 에 대해 알아보자!!! (0) | 2020.08.24 |
| PlayGround) Hashable에 대해서 알아보자 (0) | 2020.08.17 |
| PlayGround) Equatable에 대해서 알아보자 (0) | 2020.08.17 |
댓글