[알고리즘] 패스트캠퍼스 챌린지 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<T: Comparable> {
    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

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.