on
[알고리즘] 패스트캠퍼스 챌린지 14일차
[알고리즘] 패스트캠퍼스 챌린지 14일차
힙 구현
일반적으로 힙 구현시 배열 자료구조 를 활용함
를 활용함 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1
코드 참고해서 Swift로 구현해보고 테스트도 해봤다.
부모 노드 index = 자식 노드 Index / 2
이 규칙 적용해서 만듬
강의에서는 Python으로 진행되고, 배열에 nil값(None)을 첫번째 index에 넣어주는데
그냥 Root Node에 넣을 데이터를 첫번째 데이터로 넣어주었다.
class Heap { var heapArray: [T] = [] init(_ data: T) { heapArray.append(data) // index 0 heapArray.append(data) // real root node data } // insert func insert(_ data: T) { guard 0 != heapArray.count else { heapArray.append(data) heapArray.append(data) return } heapArray.append(data) var insertIndex = heapArray.count - 1 while self.moveUp(index: insertIndex) { let parentIndex = insertIndex / 2 self.heapArray.swapAt(insertIndex, parentIndex) insertIndex = parentIndex } } func moveUp(index: Int) -> Bool { guard index > 1 else { return false } let parentIndex = index / 2 if heapArray[index] > heapArray[parentIndex] { return true } else { return false } } }
Heap에서 데이터 삭제
보통은 최상단의 최대값 또는 최소값을 삭제한다.
삭제 후 가장 최하단부 왼쪽에 위치한 노드(마지막 추가한 노드)를 root node로 이동한다.
root node의 값의 child node보다 작을 경우 root node의 child node 중 가장 큰 값을 가진 노드와 root node의 위치를 바꿔주는 행위를 반복한다.
Heap 형태에서 나타날 수 있는 케이스는 세 가지이고, 각 경우에서 위의 과정 반복 시에 판단을 하고, root node와 child node 값 비교 후 데이터 swap 해주면 된다!
[나타날 수 있는 경우]
1. child node가 없는 경우
2. 왼쪽 child node만 있는 경우
3. 왼쪽, 오른쪽 child node 둘다 있는경우
#. 완전 이진트리 구조에서는 왼쪽부터 데이터가 채워지므로 [오른쪽 child node]만 있는 경우가 생길 수 없음!
삭제하는 코드도 구현해보고, 테스트도 해봤다.
잘 지워짐!
근데 코드가 너무 더럽당. .ㅎㅎ...
func pop() -> T? { if heapArray.count < 1 { return nil } let returnData = heapArray[1] heapArray[1] = heapArray.last! heapArray.removeLast() var poppedIndex = 1 while(moveDown(index: poppedIndex)) { var leftChildIndex: Int = poppedIndex * 2 var rightChildIndex: Int = poppedIndex * 2 + 1 // #2. no only right child node if rightChildIndex >= self.heapArray.count { if heapArray[poppedIndex] < heapArray[leftChildIndex] { heapArray.swapAt(poppedIndex, leftChildIndex) poppedIndex = leftChildIndex } } // #3. has both left, right child node else { if heapArray[leftChildIndex] > heapArray[rightChildIndex] { if heapArray[poppedIndex] < heapArray[leftChildIndex] { heapArray.swapAt(poppedIndex, leftChildIndex) poppedIndex = leftChildIndex } } else { if heapArray[poppedIndex] < heapArray[rightChildIndex] { heapArray.swapAt(poppedIndex, rightChildIndex) poppedIndex = rightChildIndex } } } } return returnData } func moveDown(index: Int) -> Bool { // child's node let leftChildIndex: Int = index * 2 let rightChildIndex: Int = index * 2 + 1 // #1. no left, right child node if leftChildIndex >= self.heapArray.count { return false } // #2. no only right child node else if rightChildIndex >= self.heapArray.count { if heapArray[index] < heapArray[leftChildIndex] { return true } else { return false } } // #3. has both left, right child node else { if heapArray[leftChildIndex] > heapArray[rightChildIndex] { if heapArray[index] < heapArray[leftChildIndex] { return true } else { return false } } else { if heapArray[index] < heapArray[rightChildIndex] { return true } else { return false } } } }
오늘의 인증샷! 오늘은 맥북으로 들었다.
오늘까지로 Heap 강의 끝났고,
자료구조 강의도 끝났군!!
내일부터 [알고리즘 기초] 파트로 넘어간다.
그래도 2주간 빠짐없이 매일매일 강의 잘 들었는데.. 기억에도 잘 남아잇겠ㅈ..지.?? ㅎ...?
https://bit.ly/37BpXiC
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
from http://tnqtnq.tistory.com/91 by ccl(A) rewrite - 2021-09-19 19:26:21