Heap Property (Heap Invariant)

---

• Tree 형태의 자료구조로, max, min 값을 빠르게 구하는데 특별한 특성을 가지고 있음
• heap은 완전한 이진트리이다 ⇒ binary heap 이라고 알려짐
  : 배열을 이용해 생성될 수 있다
• 가장 마지막 level을 제외하고, 모든 level이 가득 차 있어야 한다.

Max Heap

높은 우선순위를 가지는 higher value를 구성요소로 가진다

→ 최대값을 빠르게 찾아야 하는 경우 유용 (ex. 우선순위가 높은 작업을 처리할 때 자주 사용)

• Parent Node들은 Children 값들보다 크거나 같은 값을 반드시 포함해야 한다.
• Root Node는 항상 가장 큰 값을 가진다.

Min Heap

높은 우선순위를 가지는 lower value를 구성요소로 가진다.

→ 최소값을 빠르게 찾아야 하는 경우 유용함 (ex. 최소 비용 경로 탐색 알고리즘 (Dijkstra’s algorithm) )

→ 각 value를 음수 취해서 max heap 으로 처리하면 좋다

• Parent Nodes 는 항상 Children들의 값보다 작거나 같은 값을 포함해야 한다.
• Root Node는 반드시 가장 작은 값을 가진다.

활용

• 컬렉션의 최소값 혹은 최대값 구하기
• Heapsort
• 우선순위 큐 구현에서
• 그래프 알고리즘 (Prim’s, Dijkstra’s)

구현

---

Common Heap Operations

struct Heap<Element: Equatable> {

	var elements: [Element] = [] // heap 안에 요소들을 가지고 있기 위한 배열 
	let sort: (Element, Element) -> Bool // heap이 어떻게 정렬되어야 하는지 정의한 메서드
	
	init(sort: @escaping (Element, Element) -> Bool) {
		// 두 개의 요소를 비교해서 그 결과에 따라 true or false를 반환한다. 
		// true를 반환하면 첫번재 요소가 우선순위 더 높고, false 반환 시 반대. 
		self.sort = sort
	}
}

Heap을 배열로 표현하기

(왜 배열로 표시하냐? 추후 swap 작업을 좀 더 편리하게 하기 위해!)

• level이 하나 올라갈수록, 아래 level과 비교해 두 배 많은 노드를 갖게 됨
• index 계산법 (부모 노드의 index를 기준으로!)

var isEmpty: Bool {
	elements.isEmpty
}

var count: Int {
	elements.count 
}

func peek() -> Element? {
	elements.first
}

func leftChildIndex(ofParentAt index: Int) -> Int {
	(2 * index) + 1
}

func rightChildIndex(ofParentAt index: Int) -> Int {
	(2 * index) + 2
}

func parentIndex(ofChildAt index: Int) -> Int {
	(index - 1) / 2
}

Heap의 root 노드 Remove

• remove 메서드

  mutating func remove() -> Element? {
  	guard !isEmpty else { // 1. heap이 비어있는지 check 
  		return nil
  	}
  	
  	elements.swapAt(0, count - 1) // 2. root노드와 마지막 element를 swap 
  	
  	defer {
  		siftDown(from: 0) // 4. 삭제를 수행한 이후에 siftdown하면서 다시 max heap 혹은 min hep 형태로 만들어준다! (completion handler로 들어가겠지) 
  	}
  	return elements.removeLast() // 3. 마지막 element 삭제하고 반환 
  }

• siftDown 메서드

  mutating func siftDown(from index: Int) {
  	var parent = index // 1. 부모 인덱스 저장 (parent는 현재 노드가 힙 속성을 만족하도록 처리해야 하는 노드) 
  	
  	while true { // 2. 반복문 시작 (제거할 적절한 위치를 찾으면 종료되는 반복문) 
  
  		// 3. 현재 부모노드의 왼쪽 자식과, 오른쪽 자식의 인덱스를 계산해서 받는다. 
  		// 이 때, 자식노드가 존재할 수도, 존재하지 않을 수도 있다. 
  		// ex. 힙의 끝에 도달하면 자식 노드가 없을 수도 있음 
  		let left = leftChildIndex(ofParentAt: parent)
  		let right = rightChildIndex(ofParentAt: parent) 
  
  		// 4. 후보 인덱스 초기화 
  		var candidate = parent 
  
  		// 5. 왼쪽 노드가 존재하고, 왼쪽 자식의 우선순위가 부모보다 높으면 
  		if left < count && sort(elements[left], elements[candidate]) {
  			// candidate 변수에 왼쪽 자식의 인덱스 저장 
  			candidate = left
  		}
  		
  		// 6. 오른쪽 자식 노드가 존재하고, 오른쪽 자식의 우선순위가 부모보다 높으면 
  		if right < count && sort(elements[right], elements[candidate]) {
  			// candidate 변수에 오른쪽 자식 인덱스 저장 
  			candidate = right // 6
  		}
  		
  		// candidate가 parent와 같아지면 while 문 탈출 
  		if candidate == parent {
  			return // 7
  		}
  		
  		// 8. 윗 줄에서 탈출하지 못한 경우, parent와 candidate 교체 
  		elements.swapAt(parent, candidate) 
  
  		// 9. 그리고 그 candidate를 새로운 parent 로 설정 -> 비교 계속 됨 
  		parent = candidate
  	}
  }
  		

  • 주어진 인덱스의 노드를 부모 노드로 취급하고, 자식 노드들과 비교해 필요한 경우 위치를 변경하는 역할을 한다. → 이 과정에서 힙의 우선순위 규칙을 유지할 수 있다.
    

Complexity

• remove() : O(logn)
  • Swapping elements : O(1)
  • Sifting down elements : O(logn)

Heap의 root 노드 Insertion

로직

1. heap의 가장 끝에 value를 추가한다.
   

2. Max Heap 특성을 체크하기 위해 Sift Up 해준다.
   → parents 보다 더 우선순위가 높으므로 올라가야하기 때문이다.

• insert(_ element: Element)

  mutating func insert(_ element: Element) {
  	elements.append(element)
  	siftUp(from: elements.count - 1)
  }

  mutating func siftUp(from index: Int) {
  	var child = index
  	var parent = parentIndex(ofChildAt: Child)
  	while child > 0 && sort(elements[child], elements[parent]) }{
  		elements.swapAt(child, parent)
  		child = parent
  		parent = parentIndex(ofChildAt: child)
  	}
  }

임의의 (특정) 인덱스에서 Remove

• Heap
  

    struct Heap<Element: Equatable> {
    
    	var elements: [Element] = [] // heap 안에 요소들을 가지고 있기 위한 배열 
    	let sort: (Element, Element) -> Bool // heap이 어떻게 정렬되어야 하는지 정의한 메서드
    	
    	init(sort: @escaping (Element, Element) -> Bool) {
    		// 두 개의 요소를 비교해서 그 결과에 따라 true or false를 반환한다. 
    		// true를 반환하면 첫번재 요소가 우선순위 더 높고, false 반환 시 반대. 
    		self.sort = sort
    	}
    }

• remove

mutating func remove(at index: Int) -> Element? {

	// 1. 파라미터로 받는 index가 Heap 내부 elements 배열의 개수 안에 있는지 체크 
	// 아니라면 nil 반환해서 탈출 
	guard index < elements.count else {
		return nil  
	}
	
	// 2. index 가 배열의 가장 마지막 요소일 때, 마지막 값을 반환 
	if index == elements.count - 1 {
		return elements.removeLast() 
	}
		
		// 3. 마지막 요소가 아니라면, 마지막 요소와 index 요소를 swap 
		 else {	
		elements.swapAt(index, elements.count - 1) 
		
		defer {
			/* 5-1. 루트에 지금 가장 작은 값이 있을 확률이 높음. 
							자식노드로 내려가면서 노드의 적절한 위치를 찾는다. 
			*/
			siftDown(from: index)
			
			/* 5-2. siftDown 이후, 자식 노드에서 부모 노드로 올라가며 힙 속성을 유지한다. 
			*/
			siftUp(from: index) // 다시 올라가면서 부모보다 큰 child 가 있는 경우를 재조정 
		}
		
		// 4. 교체된 이후에 마지막 요소가 되니까 삭제 
		return elements.removeLast()
	}
}

위 메서드에서 mutating이 붙는 이유와, 이렇게 구조체 인스턴스의 값을 변경할 때 성능에는 영향을 미치지 않을지에 대한 궁금증이 생겼다.

mutating 과 구조체, 그리고 COW (Copy-on-Write)

• mutating 키워드가 붙는 이유
  • struct 구조체는 값 타입이라서 struct 내부의 인스턴스 속성을 수정할 수 없다. (기본적으로 제공되지 않는다. )
  • 그러나 위 메서드처럼 인스턴스를 수정해야 할 필요가 있을 때는 메서드 앞에 mutating 키워드를 붙이면 된다.
    
    
• 그럼 성능 면에서는 어떨까? / 기존과 어떻게 다르게 동작하는걸까?
  • mutating메서드는 복사된 구조체 인스턴스에서 변경을 수행하고, 그 변경된 인스턴스를 다시 돌려주는 방식으로 동작함
    
    
• COW (Copy-on-Write)
  • 구조체는 데이터가 복사되는 과정에서 값의 크기에 따라 복사 비용이 소요될 수 있어 성능에 영향을 미칠 수 있음
  • 하지만 Swift에서 사용하는 Copy-on-Write 최적화를 사용하면, 구조체가 복사되더라도 실제로 변경이 일어나지 않는 한, 복사는 이뤄지지 않고 “참조만 공유됨”
  • 결국, mutating 메서드 호출해서 값을 실제로 변경하려는 시도를 할 때, 그 순간에 “진짜 복사”가 발생한다.
    
    ⇒ 이 최적화로 인해 복사 비용 크게 발생하지 않고 구조체는 효율적으로 동작이 가능함

또한 `defer`가 흐름 상 가장 함수 호출 시 반환 이후에 실행되는데, 이것이 `escaping closure` 와는 어떻게 다른지 비교해보았다.

Defer vs Escaping Closure

• defer
  • 코드의 실행 흐름과 관계없이 반드시 실행되어야 하는 코드가 있을 때 유용함
    ex. 자원 해제, 파일 닫기, 네트워크 연결 해제 등 어떤 작업의 마무리 작업 시
  • 함수가 끝날 때 반드시 실행됨 → 함수가 여러 경로로 종료될 수 있는 상황에서 꼭 실행해야 하는 코드가 있을 때 유용함
    (오류, 예외처리 등으로 함수가 예기치 못하게 종료 될 떄도 실행할 수 있으므로)
  • 장점
    • 반드시 실행을 보장함
      
      
• Escaping Closure
  • 코드의 실행을 나중으로 미루거나, 필요한 곳에서 호출을 예약할 때 유용함
  • 주로 비동기 작업에서 자주 사용됨
  • 명시적인 호출이 필요하다!!

Heap에서 element 요소 검색하기

1. 요소의 index 검색하기

func index(of element: Element, startingAt i: Int) -> Int? {

	if i >= count {
		return nil  // 1.
	}
	
	// 2. 찾고 있는 요소가 현재 요소보다 우선순위가 높은지 체크 
	if sort(element, elements[i]) {
		return nil // 왜 nil을 반환할까? 찾고 있는 요소가 current보다 우선순위가 높다는게 어떤 의미일까? 
	}
	
	if element == elements[i] {
		return i // 3. 요소를 찾았을 때 해당 인덱스 반환 
	}
	
	
	// 4. 재귀적으로 왼쪽 노드를 쭉 동일하게 호출 
	if let j = index(of: element, startingAt: leftChildIndex(ofParentAt: i) {
			return j  
		}
	
	// 5. 재귀적으로 오른쪽 노드를 쭉 호출 (같아질 때 까지) 
	if let j = index(of: element, startingAt: rightChildIndex(ofParentAt: i)) {
		return j 
	}
	return nil // 6. 모두 실패하는경우 nil 반환 
}

주석 2번 단계에서의 의문 : 현재 노드가 우선순위가 찾고자 하는 요소보다 높다는게 무슨 의미일까?

• 현재 노드보다 더 높은 우선순위를 가진 요소를 존재하지 않는다. (항상 부모가 자식보다 높은 우선순위를 가지니까 더 내려가봐야 찾을 수 없음)
• 현재 노드가 element 보다 우선순위가 높다면, element가 힙에 존재할 가능성이 없으므로 탐색 계속할 필요가 없다

시간복잡도

Priority Queues

---

• 요소들이 들어온 순서대로 처리되는 것이 아닌, 요소들의 “우선순위”에 따라 처리되는 자료구조.
• 우선순위가 높은 요소가 먼저 처리된다. (응급실 같은 것)

→ 주어진 요소들 중 최댓값 또는 최솟값을 빠르게 찾고 처리해야 하는 상황에 유용함

• 활용
  • Dijkstra’s algorithm : 최단 경로 계산 시, 최소 비용을 계산함
  • A pathfinding algorithm : 탐색 중 가장 짧은 경로를 찾을 때 탐색할 경로의 우선순위를 관리함
  • Heap sort : 요소들을 정렬
  • Huffman coding : 압축 트리 만들 떄, 아직 부모 노드가 없는 가장 작은 빈도를 가진 두 노드를 계속 찾아 결합하는데 사용함

1. Max-priority queue
가장 큰 값이 큐의 앞에 있어서 가장 먼저 처리됨

2. Min-priority queue
가장 작은 값이 큐의 앞에 있어서 가장 먼저 처리됨

Dequeue

0번째 index 제거 (root 노드 : 우선순위 가장 높은 요소를 제거하는 것)

1. 가장 우측 하단의 leaf 를 root로 올리고, length 1 줄인다
2. SiftDown

Enqueue

1. length 1 늘리고, 새로운 요소를 배열 끝에 저장한다
2. Sift Up (힙 특성 유지하기 위해 root에 도달하거나, 적당한 부모를 만날 때 까지 위치를 이동한다)

구현방법

Sorted Array

• 찾을 때 : O(1)
• 삽입할 때 : O(n)

Balanced binary Search Tree → enqueue, dequeue 가 효율적

• 이중 우선순위 큐를 만들 떄 유용함 → 최소값과 최대값을 O(log n) 시간 내에 모두 얻을 수 있음
• 삽입도 sorted array보다 빠름 → O(logn)

Heap

• 정렬할 필요가 없기 때문에 배열보다 효율적이다.
• 모든 힙 연산 : O(logn)
• 최소값 혹은 최대값 : O(1)