Heap (4) 썸네일형 리스트형 [Swift] Heap을 이용한 Priority Queue 구현 우선순위 큐(Priority Queue)는 이름에서 알 수 있듯이 큐(Queue)의 일종이다. 큐는 지난 포스팅에서 설명한 것과 같이, 먼저 입력된 데이터가 먼저 출력되는 자료구조이다. 이에 반해 우선순위 큐는 출력될 데이터가 입력된 순서에 따라 결정되는 것이 아니라, 우선순위에 따라 이루어진다는 차이가 있다. 우선순위 큐도 다양한 방법으로 구현할 수 있지만, 힙으로 구현하는 것이 적절해 보인다. 배열(Array)이나 연결 리스트(Linked List)로 구현할 경우, 삽입 또는 삭제 연산 시에 데이터의 정렬을 위해 모든 데이터를 순회해야 하기 때문에 시간 복잡도가 O(n)이 소요된다. 하지만 힙의 경우 삽입 또는 삭제 시에 반정렬 상태만 유지하면 되는 완전 이진 트리이기 때문에 시간 복잡도가 O(lb(.. [Swift] Array를 이용한 Heap 구현 3 - 함수형 프로그래밍 힙에 대한 배경 지식 및 구현은 아래 포스팅들을 참고하면 된다. https://taeminator1.tistory.com/43 https://taeminator1.tistory.com/44 길고 긴 여정이었지만, 이제 힙에 대한 구현은 마지막 포스팅이 될 것 같다. 이번 포스팅의 주제는 "다양한 힙 구현하기"이다. 지난 포스팅에서는 "최대 힙"을 구현했지만, 때로는 다른 종류의 힙을 원할 수도 있다. 먼저 최소 힙을 구현하는 방법에 대해 생각해 보자. 간단히 설명하자면, 최소 힙(Min Heap)은 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 말한다. 이러한 힙을 구현하기 위해서는 아래와 같이 이전에 구현한 Heap 클래스에서 몇 개의 부등호의 방향만 변경해 주면 된다. func insert(.. [Swift] Array를 이용한 Heap 구현 2 - 최대 힙 지난 포스팅(https://taeminator1.tistory.com/43)에 이어 이번 시간에는 Swift를 이용해 힙을 실제로 구현해 보겠다. 먼저 힙을 구성하는 노드(연결 리스트에서 사용한 노드와 구별하기 위해 Heap Node라고 이름을 지었다)를 구현해 주겠다. 연결 리스트에서 구현해 준 노드 클래스와 마찬가지로 제네릭을 이용해 다양한 타입에 대응되게 만들었다. 다만 연결 리스트의 노드와 달리 힙 노드는 노드 간에 값을 비교해야 하기 때문에 Comparable 프로토콜을 준수하여 구현하였다. class HeapNode: Comparable { var data: T init(_ data: T) { self.data = data } func getData() -> T { return data } f.. [Swift] Array를 이용한 Heap 구현 1 - 개요 해당 포스팅에 앞서 트리에 대한 전반적인 정리는 이전 포스팅(https://taeminator1.tistory.com/42)을 참고하면 된다. 힙은 단말 노드가 아닌 각각의 노드에 대해 노드의 값이 자식 노드의 값과 비교해 일정한 규칙을 갖는 완전 이진 트리이다. (노드의 값(키)은 중복이 가능하다) 힙은 대표적으로 최대 힙과 최소 힙이 있는데, 자식 노드의 값이 부모 노드의 값 보다 크지 않은 힙을 최대 힙(Max Heap), 자식 노드의 값이 부모 노드의 값 보다 작지 않은 힙을 최소 힙(Min Heap)이라고 한다. 이번 포스팅에서는 특별한 언급이 없다면 최대 힙(각각의 부모 노드의 값이 자식 노드의 값보다 크거나 같은 경우)으로 가정하고 힙에 대한 설명을 이어 나가겠다. 힙의 가장 큰 특징은 반정.. 이전 1 다음
