[스위프트:자료구조] Heap: 힙 자료구조 (1 / 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 과는 다른 용어임을 유의. Heap 메모리는 여기
• 정의 by 나무위키

Heap 의 요구조건

• 이를 Heap Property 혹은 Heap invariant 라고 표현한다. ( 원서 보면 이렇게 나와있어~ )

• 1.
• Max Heap 의 경우 부모노드의 값은 항상 자식노드의 값보다 크거나 같아야 한다. 루트 노드의 값은 항상 가장 큰 값을 가지고 있다.
• Min Heap 의 경우 부모노드의 값은 항상 자식노드의 값보다 작거나 같아야 한다. 루트 노드의 값은 항상 가장 작은 값을 가지고 있다.
• 2.
• Heap 은 완전 이진 트리이다. ( Complete binary tree )
• 완전이진트리란 마지막 레벨의 노드를 제외하고 나머지 모든 레벨의 노드들이 빈틈없이 채워진 이진트리를 표현한 것
• 아래 그림과 같다.

Heap 을 활용한 것들

• 최대 최소를 계산할 때!

• Heap Sort ( 힙 정렬 )

• Priority Queue 에 활용됨

• 또 이 Priority Queue 는 그래프 알고리즘인 prim 이나 Dijkstra 알고리즘에서 활용되므로 Heap 은 이 알고리즘 들의 기초개념이 되는 것.

그래서 어떻게 Heap을 컴퓨터로 표현할건데?

• 이진 트리로 표현할 수도 있지만?
• 배열로도 표현할 수 있는데 배열로 표현하면 아래와 같은 장점이 있어.
• 힙의 값들이 메모리 안에서 모두 함께 저장되기 때문에 시간복잡도와 공간복잡도 측면에서 효율적이다. ( 시간복잡도와 공간복잡도 모른다면 더 효율적이라는 말. )
• 메모리 안에 함께 저장된다는 것은 배열의 특징이야. 스위프트가 구현한 표준라이브러리의 Array 는 그러한 특징을 같는 효율적인 구조체임.
• 결론은 배열로 표현할 거임.
• 트리에서 원하는 노드를 탐색하는 효율은 O( log n ) 
• Random Access Data Structure 에서 원하는 값을 탐색하는 효율은 O(1) 
• Random Access Data Structure 은 스위프트에서 정의한 프로토콜로 Array 는 이 프로토콜을 채택한다.
• 이 프로토콜 이란 개념을 잘 모른다면 스위프트에서 배열인 Array 구조체가 값 탐색하는 효율이 O(1) 이라고 생각하면 깔끔!

Array 로 표현한 Heap 이해하기

                               이진 트리 구조로 만들어진 Heap             ㅡㅡㅡㅡㅡㅡㅡ>ㅡㅡㅡㅡㅡㅡㅡ>                         배열로 표현한 Heap

• 위에서 보는 것과 같이 트리의 레벨이 올라갈 수록 이전 레벨 보다 2배씩 노드의 수가 증가한 다는 것을 볼 수 있지?

• 이를 토대로 원하는 값의 왼쪽, 오른쪽 자식 노드를 찾을 때 아래와 같은 규칙으로 찾을 수 있음.

• 해당 노드의 인덱스를 i 라고 할 때

• 해당 노드의 왼쪽 자식 노드의 인덱스는 2i + 1 

• 해당 노드의 오른쪽 자식 노드의 인덱스는 2i + 2

• 해당 노드의 부모 노드의 인덱스는 i -1 / 2

• 그림으로 보여줄게

• 

구현은 여기에서

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