[Data Structure / Algorithms] Heaps

전성훈·2023년 11월 9일
Algorithmsdatastructureswift
0

Data Structure-Algorithm

목록 보기
18/35

주제: 우선순위를 다루는 방법

Heaps

What is a heap?

  • 힙(Heap)은 큰 값이나 작은 값 중 가장 높은 우선순위를 빠르게 처리하기 위해 특별한 속성을 가진 트리 기반 자료구조입니다.
  • 힙은 배열을 사용하며 완전 이진 트리(Complete Binary Tree)로, 이진 힙(Binary Heap)이라고도 불립니다.
  • 힙에는 아래와 같이 두 가지 유형이 있습니다.
    1. 최대 힙(Max heap): 값이 더 큰 요소가 높은 우선순위
    2. 최소 힙(Min heap): 값이 더 작은 요소가 높은 우선순위

The heap property (힙의 특성)

  • 힙은 필수적인 특성이 있는데 이는 항상 만족해야합니다. 이러한 특성은 힙 불변성(Heap invariant)또는 힙 특성(Heap property)라고 합니다.
  • 최대 힙의 경우, 부모 노드는 항상 자식 노드보다 크거나 같은 값이어야 합니다.
  • 최소 힙의 경우, 부모 노드는 항상 자식 노드보다 작거나 같은 값을 가지고 있어야 합니다.
  • 힙은 거의 완전한 이진 트리이며, 이는 마지막 레벨을 제외한 모든 레벨이 꽉 채워져 있어야 한다는 것을 의미합니다.

Heap applications (힙의 활용)

  1. 컬렉션에서 최소 또는 최대 요소 계산하기
  2. 힙 정렬(Heap Sort)
  3. 우선순위 큐(Priority Queue)
  4. 우선순위 큐를 이용한 프림(Prim)또는 다익스트라(Dijkstra)와 같은 그래프 알고리즘

구현

struct Heap<Element: Equtable> { 
	var elements: [Element] = []
	
	let sort: (Element, Element) -> Bool 
	
	init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = []) { 
		self.sort = sort 
		self.elements = elements
	}
}
  • 트리는 자식을 참조하는 노드를 보유하며 이진 트리의 경우, 이는 왼쪽 자식과 오른쪽 자식을 가리키는 참조입니다. 힙도 이진 트리이지만, 이진 트리를 간단한 배열로서 구현할 수 있습니다.
  • 이러한 표현은 트리를 구현하는 데 활용했던 일반적인 방법과는 다소 다른 것처럼 보일 수 있지만, 힙 구현의 한 가지 이점은 요소가 모두 메모리에 같이 저장되므로 효율적인 시간 및 공간 복잡도를 가집니다.
  • 배열을 사용하여 요소를 교환하는 것은 이진 트리 자료 구조보다 더 쉽습니다.

세부 구현

  • 0을 기준으로 한 인덱스 i의 노드가 주어졌을 때
    • 왼쪽 자식: 2i + 1
    • 오른쪽 자식: 2i + 2
  • 노드의 부모를 나타낼 때
    • floor((i-1)/2)
  • 배열과 같은 랜덤 액세스 데이터 구조에서는 자식을 얻기 위한 탐색 작업은 O(1) 시간 복잡도를 나타냅니다.
extension Heap { 
	var isEmpty: Bool { 
		elements.isEmpty
	}
	
	var count: Int { 
		elements.count
	}
	
	func peek() -> Element? { 
		elements.first
	}
	
	private func leftChildIndex(ofParentAt index: Int) -> Int { 
		(2 * index) + 1
	}
	
	private func rightChildIndex(ofParentAt index: Int) -> Int { 
		(2 * index) + 2 
	}
	
	private func parentIndex(ofChildAt index: Int) -> Int { 
		(index - 1) / 2
	}
}

Remove

  • 기본적인 힙의 삭제 작업은 힙에서 루트 노드를 삭제합니다.
    1. 루트 노드를 마지막 요소와 교환합니다.
    2. 두 요소를 교환한 후, 마지막 요소를 제거하고 제거된 값을 반환합니다.
    3. 힙의 max,min heap 규칙에 의해 다시 힙의 구조를 재조정하며, 이때 sift down을 수행합니다.
  • remove()의 시간 복잡도는 O(log n)의 시간 복잡도를 나타낸다. 
extension Heap { 
	mutating func remove() -> Element? { 
		guard !isEmpty else { 
			return nil 
		}
		elements.swapAt(0, count - 1)
		defer { 
			siftDown(from: 0)
		}
		
		return elements.removeLast()
	}
	
	private mutating func siftDown(from index: Int ) { 
		var parent = index 
		
		while true { 
			let left = leftChildIndex(ofParentAt: parent)
			let right = rightChildIndex(ofParentAt: parent)
			
			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 
			}
			
			elements.swapAt(parent, candidate)
			parent = candidate
		}
	}
}

Insertion

  1. 먼저, 값을 Heap의 끝에 추가합니다.
  2. 그리고, 새로 삽입한 노드가 부모 노드보다 우선순위가 높을 수 있으므로, Heap 속성을 확인하며, 이 때 sift up을 수행합니다.
  • 시간 복잡도는 O(log n)이다. 
extension Heap { 
	mutating func insert(_ element: Element) { 
		elements.append(element)
		siftUp(from: element.count - 1)
	}
	
	private mutating func siftUp(from index: Int) { 
		var child = index 
		var parent = parentIndex(ofChildAt: child)
		whild child > 0 && sort(elements[child], elements[parent]) { 
			elements.swapAt(child, parent)
			child = parent
			parent = parentIndex(ofChildAt: child)
		}
	}
}

Removing from an arbitrary index(임의 인덱스)

  1. 해당 인덱스가 배열 범위 내에 있는지 확인합니다. 그렇지 않으면 nil을 반환합니다.
  2. 제거하려는 원소가 힙에서 마지막 원소라면 해당 원소를 그냥 제거합니다.
  3. 마지막 원소가 아닌 경우, 해당 원소를 마지막 원소와 교환합니다.
  4. 마지막 원소를 반환하고 제거합니다.
  5. siftDown, siftUp을 활용해서 힙을 재조정합니다.
    • ex) leaf 원소가 제거될 때 siftUP, 중간 원소가 제거될 때 siftDown
mutating func remove(at index: Int) -> Element? { 
	guard index < elements.count else { 
		return nil 
	}
	
	if index == elements.count - 1  {
		return elements.removeLast()
	} else { 
		elements.swapAt(index, elements.count - 1)
		defer { 
			siftDown(from: index)
			siftUp(from: index)
		}
	}
	return elements.removeLast()
}
  • 힙은 빠른 검색을 위해 설계되지 않았습니다. 이진 탐색 트리에서는 O(log n) 시간 내에 검색을 수행할 수 있지만, 힙은 배열을 사용하고, 배열의 값도 정렬되어 있지 않기 때문에 이진 검색을 수행할 수 없습니다.
  • 그렇기 때문에 힙의 검색 시간 복잡도는 O(n)을 나타낸다. 
func index(of element: Element, startingAt i: Int) -> Int? { 
	if i >= count { 
		return nil
	}
	// 더 높은 우선순위를 검색할 때
	if sort(element, elements[i]) { 
		return nil 
	}
	
	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 
}

Building a heap

  • initializer는 추가 매개변수를 받습니다. 비어 있지 않은 배열을 제공되면, 이를 Heap의 요소로 활용합니다. heap의 속성을 유지하기 위해, 배열을 역순으로 루프를 돌며 첫 번째 non-leaf 노드부터 시작하여 모든 부모 노드를 sift Down 을 수행합니다.
  • 이때 leaf 노드를 sift Down 하는 것은 의미가 없기 때문에 요소의 반만 루프를 돕니다.
init(sort: @escaping (Element, Element) -> Bool, elements: [Element] = [] ) { 
	self.sort = sort
	self.elements = elements
	
	if !elements.isEmpty { 
		for i in stride(from: count / 2 - 1, through: 0, by: -1) { 
			siftDown(from: i)
		}
	} 
}
var heap = Heap(sort: >, elements: [1,12,3,4,1,6,8,7])
var heap2 = Heap(sort: <, elements: [1,12,3,4,1,6,8,7])

print(heap)
print(heap2)

Heap<Int>(elements: [12, 7, 8, 4, 1, 6, 3, 1], sort: (Function))
Heap<Int>(elements: [1, 1, 3, 4, 12, 6, 8, 7], sort: (Function))

결론

  • 힙은 우선순위를 유지하는데 좋습니다.
  • 힙의 요소는 간단한 공식을 활용하여 메모리에 패킹됩니다.
  • 요소를 삽입하거나 제거할 때마다 힙의 힙 속성을 유지해야 합니다.
OperationsTime Complexity
removeO(log n)
insertO(log n)
searchO(n)
peekO(1)

출처(참고문헌)

제가 학습한 내용을 요약하여 정리한 것입니다. 내용에 오류가 있을 수 있으며, 어떠한 피드백도 감사히 받겠습니다.

감사합니다

profile
전성훈
이전 포스트

[DataStructure / Algorithm] Binary Search

다음 포스트

[Data Structure / Algorithms] Priority Queues

0개의 댓글