[스위프트:자료구조] Heap: 힙 자료구조 (2 / 2) : Heap 구현하기

안녕하세요 !  씩이 입니다!

저는 Swift 와 iOS 를 공부하고 연구하는 학생입니다.

같은 분야를 공부하는 분들에게 조금이라도 도움이 주고 싶어서 공부하는 것들을 공유합니다.

제 3자가 있다고 가정하고 설명하기 때문에 존대를 하지 않는점 이해 부탁드립니다.

공유가 미래 라고 생각합니다. 

한국의 모든 개발자분들 존경합니다!

---

• Swift version : Swift 4.2  Swift 언어
• 참고한 것들
• DataStructures and Algorithms in Swift
• Swift-Algorithm-club 깃허브 
• 스위프트 데이터 구조와 알고리즘
• Youtube
• 칸 아카데미

• 씩이 Github
• 자료구조 소스파일 있습니다.
• iOS 관련 자료들, 정보들 정리해 두었습니다.

• 스위프트로 구현한 자료구조 : DataStructures in Swift4
• Swift4 : 연결리스트 (1 / 3) : #LinkedList : #DataStructrue : #자료구조
  
• Swift4 : 연결리스트 (2 / 3) : #LinkedList : #값 추가하기, push, append : #값 삽입하기,insert
• Swift4 : 연결리스트 (3 / 3) : #LinkedList : #값 제거하기, pop, removeLast, remove(at: )
• [스위프트 : 자료구조] 스택: Stack: 자료구조: DataStructure: 쌓기
• [스위프트 : 자료구조] 스택 : Stack : 프로토콜 지향 스택 구현하기
• [스위프트 : 자료구조] 큐 (1 / 4): Queue: #자료구조: #배열로 구현한 큐: #배열의원리
• [스위프트 : 자료구조] 큐 (2 / 4): Queue: #자료구조: #연결리스트: #더블연결리스트: #DoublyLinkedList
• [스위프트 : 자료구조] 큐 (3 / 4): Queue: #자료구조: #Stack으로 구현: #더블스택: #DoubleStack: #제일좋음
• [스위프트 : 자료구조] 큐 (4 / 4): Queue: #자료구조: #RingBuffer: #링버퍼로 구현한 큐: #고정된배열: #마지막!!
  
• [스위프트 : 자료구조] 큐: Queue: 프로토콜 지향 큐 구현하기
• 스위프트: 트리: Tree: #자료구조: #깊이우선탐색: #레벨정렬탐색: #검색알고리즘: Swift4
• 스위프트: 이진 탐색 트리(1 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• 스위프트: 이진 탐색 트리(2 / 2): #BinarySearchTree: #자료구조: #배열과 비교: #트리: #탐색: #삽입: #삭제
• [스위프트 : 자료구조] AVL Tree: 자가 균형 트리: #balance: #트리의 높이: #rotation메소드: #성능오짐
• [스위프트:자료구조] 트라이: Trie: 문자열 찾기: 단어 찾기
  
• [스위프트:자료구조] Heap: 힙 자료구조 (1 / 2) : Heap 이란?
  
• [스위프트:자료구조] Heap: 힙 자료구조 (2 / 2) : Heap 구현하기
  

• 스위프트로 구현한 알고리즘 : Algorithms in Swfit4
• [스위프트 : 알고리즘] 재귀호출 (1 / 6) : recursive: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 팩토리얼 (2 / 6) : factorial: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 거듭제곱 (3 / 6) : Power: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트 : 알고리즘] 재귀 : 피보나치 수열(4 / 6) : Fibonacci: 재귀호출 : 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 하노이의 탑 (5 / 6) : Hanoi: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
  
• [스위프트 : 알고리즘] 재귀 : 최대공약수 (6 / 6) : GCD: 재귀호출: 재귀함수: 반복문: 팩토리얼: 거듭제곱: 피보나치: 하노이의 탑: 최대공약수
• [스위프트:알고리즘] 이진 탐색[1 / 3]: Binary Search: 이진 탐색이 뭐야?
  
• [스위프트:알고리즘] 이진 탐색[2 / 3]: Binary Search: 이진 탐색: 반복문, 재귀호출로 구현하기
  
• [스위프트:알고리즘] 이진 탐색[3 / 3]: Binary Search: 이진 탐색: 프로토콜 지향으로 구현하기

• Swift 주제별 분류
• [컴퓨터 네트워크] 인터넷이란 무엇일까?
• [스위프트] 데이터 구조와 알고리즘을 배우는 이유
• Swift4 : 제어 전달 명령문( Control Transfer Statement ) : #continue, #break, #return 키워드
• Swift4 : 클래스와 구조체 : #값을 대하는 방식 : #참조타입, 값 타입 : #===
• Swift4 : 프로퍼티 : #Property : #get, set : #willSet, didSet
• Swift4 : 메소드 : #Method : #영향력 범위 : #self : #mutating : #값타입 수정
• Swift4 : 프로토콜 1 : #Protocol : #설계 : #요구사항 : #델리게이트 패턴 전처리 (1 / 2)
• Swift4 : 프로토콜 2 : #델리게이트 패턴 : #델리게이션 (2 / 2)
• Swift4 : 제네릭 : #Generics : #왜필요해? : #where키워드 : #제약사항걸기
• Swift4 : 자동 참조 카운팅 : #Automatic Referece Counting : #ARC :#강한참조 : #Strong Reference Cycle : #메모리 누수
• Swift4 : 클로저: Closure: #표현방식: #왜필요해?: #효율적: #간결성: #생략
• [스위프트 : 기초] 서브스크립트 : Subscript : 지름길
  
  
  

Heap DataStrcutrue: 힙 자료구조 

Heap 이 뭐야?  ( 1 / 2 )

Heap 구현하기 ( 2 / 2 )

Heap 큰 그림은 다음과 같아

• 준비단계 : Convenience Properties and Methods
• remove(): 제거 메소드
• siftDown(from: ) : 아랫쪽 기준으로 Heap 구조 만드는 메소드, sift 는 채로 거르다 라는 뜻으로 필터링해서 원하는 노드를 적절한 곳에 위치시키는 역할
• insert(): 삽입 메소드
• siftUp(from :) : 윗쪽 기준으로 Heap 구조 만드는 
• remove(at: ) : 특정 인덱스의 노드 제거하려는 메소드
• index(of: startingAt: ) : 값을 입력받고 해당 값을 가지는 노드의 인덱스 찾는 메소드

준비단계 : Convenience Properties and Method

struct Heap<Element: Comparable> { 
// 값에 Comparable 프로토콜 채택하게한 건 sort 에 <,> 넣을 거라서
    
    var elements: [Element] = [] 
// 배열로 구현할거야.  트리는 O(log n) / 배열은 O(1) random access
    let sort: (Element, Element) -> Bool // 함수임 , < 이나 > 용도로 쓸거임 
    
    init(sort: @escaping (Element,Element) -> Bool, elements: [Element] = []) { 
        // sort 에 < , > 넣는거 개꿀딴지^^ 
        // @escaping 키워드는 아래에 따로 설명
        self.sort = sort
        self.elements = elements
        
        if !elements.isEmpty {
            for i in stride(from: elements.count / 2 - 1, through: 0, by: -1){
                // 랜덤한 배열을 Heap 구조로 바꿈
                // stride 는 글로벌함수로 for 문의 반복 설정할때 
                siftDown(from: i)
            }
        }
    }
    
    var isEmpty: Bool {
        return elements.isEmpty
    }
    
    var count: Int {
        return elements.count
    }
    
    func peek() -> Element? {
        return elements.first
    }
    
    func leftChildIndex(ofParentAt index: Int) -> Int {
        return 2*index + 1
    }
    
    func rightChildIndex(ofParentAt index: Int) -> Int {
        return 2*index + 2
    }
    
    func parentIndex(ofChildAt index: Int) -> Int {
        return (index - 1) / 2
    }
 

• @escaping :  클로져가 함수의 매개변수로 쓰일 때 그 함수가 리턴한 후에도 클로져가 호출될때 escaping 이 필요하다.
• 자세한 사항 여기에서 escaping 검색 하면 나옵니다~

remove() , siftDown() 

    mutating func remove() -> Element? { 
    // swap 은 O(1) 이고 sifhDown 은 O(log n) 이라서 전체 시간복잡도 O(log n)
        guard !isEmpty else { // 비어있지 않으면 삭제 연산 진행할것
            return nil
        }
        elements.swapAt(0, count - 1) // Array 의 swapAt 메소드 활용 
        defer { 
            // defer 키워드는 { } 실행구문 안의 로직을 가장 마지막에 실행하도록 순서를 보장해주는 역할
            // 어디 위치에 있어서 실행 순서는 가장 마지막.
            siftDown(from: 0) // 루트노드 sift Down 
        }
        return elements.removeLast() // 삭제할 노드 삭제후 반환하기.
    }
    
    mutating func siftDown(from index: Int) {
        // 이 메소드가 실행될 시점에선 배열의 가장 크거나 작은 놈이 루트노드가 되어있는 시점임.
        var parent = index
        
        while true {
            let left = leftChildIndex(ofParentAt: parent)
            let right = rightChildIndex(ofParentAt: parent)
            // left, right 가 parent 가 변함에 따라 변하니까 var 라고 하기 쉬운데 
            // while 의 { } 입장에서는 변하지 않는 값이므로 let 임을 유의
            
            var candidate = parent // 탐색할 아이 지정
            if left < count , sort(elements[left], elements[candidate]) {
                // 왼쪽 자식노드가 있고, 그 자식노드 값이 부모노드 값보다 크다면
                candidate = left
            }
            if right < count , sort(elements[right], elements[candidate]) {
                candidate = right
            }
            if candidate == parent {  // 종료조건
                // return 만날때까지 무한반복, 위의 조건에 부합하지 않는 순서일 때 return 하는 것.
                return
            }
            elements.swapAt(parent, candidate)
            parent = candidate
        }
    }
 

insert(), siftUp()

    mutating func insert(_ element: Element) {
    // append 는 O(1), siftUp 은 O(log n) 이므로 전체 효율은 O(log n)
 
        elements.append(element)
        siftUp(from: elements.count - 1)
        
    }
    
    mutating func siftUp(from index: Int) {
        var child = index // 마지막 인덱스
        
        while true {
            let parent = parentIndex(ofChildAt: child) 
            
            if child > 0 && sort(elements[child], elements[parent]) { // > 이니까
                elements.swapAt(child, parent)
                child = parent
            }else {
                return
            }
        }
        /* // 이렇게도 작성할 수 있음.
        var parent = parentIndex(ofChildAt: child)
        while child > 0 && sort(elements[child], elements[parent]) {
            
            elements.swapAt(child, parent)
            child = parent
            parent = parentIndex(ofChildAt: child)
        }*/
    }

remove(at: ) : 임의의 노드 제거하기.

    mutating func remove(at index: Int) -> Element? {
        guard index < elements.count else {  return nil } 
        // 위에 정의한 count 를 쓰지않은 이유는 count 는 Heap 인스턴스에서 count를 알려고 하는 거고 
        // 인스턴스의 메소드가 실행될떄마다 값이 바뀔 가능성 있음.
        
        if index == elements.count - 1 {
            return elements.removeLast()
        }else {
            elements.swapAt(index, elements.count-1) // 제거하려는 값은 맨 뒤로 보내기~
            siftDown(from: index) // index 자리 기준으로 아랫쪽 재정렬
            siftUp(from: index) // index 자리 기준으로 위쪽 재정렬
        }
        return elements.removeLast() 
    }

index(of: , startingAt: ) : 주어진 값에 해당하는 인덱스 찾기, 범위까지 설정함

    // 모든 노드 한번씩 탐색해야 하기 때문에 O(n) 최악
    // 탐색 메소드는 트리는 O(log n) 임. 배열이 더 안좋아.
    func index(of element: Element, startingAt i:Int) -> Int? {
        // 값, 시작 인덱스를 주고 , 값에 해당하는 인덱스 있으면 인덱스 반환 , 없으면 nil 
        // 모든 경우의 수 다 생각해야함 ㅠㅠ. 극혐
        if i >= count {
            return nil
        }
        if sort(element, elements[i]) {
            // max heap 이면 > , min heap 이면 <  인데
            // > 이면 elements[i] 이 max 인데 찾고자 하는 element 가 더 크므로 범위 초과
            // < 이면 elements[i] 이 min 인데 찾고자 하는 element 가 더 작으므로 범위 초과
            return nil 
        }
        if element == elements[i] { // 값 찾았을 때
            return i
        }
        if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i)) {
            // 왼쪽으로 재귀호출 이진 트리 탐색이랑 원리가 같음.
            return j
        }
        if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
            // 오른쪽으로 재귀호출
            return j
        }
        return nil
    }

전체 소스 코드