Heap

Heap Data Structure 

 

Heap은 각 상위 노드와 해당 하위 노드 사이에 고정된 관계가 있는 트리 기반 데이터 구조다.

 

최대 Heap의 경우 이는 상위 노드의 값이 해당 하위 노드보다 크거나 같아야 함을 의미한다. 이는 루트 노드가 항상 최댓값을 갖는다는 것을 의미한다.

 

최소 Heap의 경우 루트 노드는 항상 가장 작은 값을 갖는다.

 

 

Heap을 왜 사용하는가

 

힙을 유용하게 만드는 몇 가지 주요 속성은 다음과 같다.

1. 주어진 "n" 값 집합의 최댓값 또는 최솟값을 O(1) 시간 내에 찾을 수 있다. 배열 기반 목록을 사용하는 경우 일반적으로 O(n) 시간이 걸린다.
2. 값을 추가하고 제거하는 데는 O(log(n)) 시간이 걸리며, 최대 또는 최소 힙 속성을 유지한다. 이는 힙 정렬을 사용하여 항목 목록을 정렬할 때 사용되며, 각 요소는 한 번에 하나씩 힙에 삽입된다.

 

 

Go 표준 라이브러리 Heap Interface를 사용해 보자

힙 인터페이스를 구현하여 일반 항목 목록을 힙으로 변환할 수 있다.

 

힙 인터페이스에는 5가지 메서드가 있으며 `container/heap`라이브러리에서 제공하는 함수를 사용할 수 있다.

예를 들어 정수 목록에 대한 힙 인터페이스를 어떻게 구현할 수 있는지 살펴보자.

 

 

intHeap유형이 인터페이스를 구현했으므로 'container/heap  패키지'에서 제공하는 기능을 heap.Interface 사용하여 다양한 작업을 수행할 수 있다.

 

인스턴스를 Heap화 해보자.

 

번호가 반드시 순서대로 되어 있는 것은 아니다. 오히려 다음과 같은 힙 데이터 구조로 배열된다.

 

 

Heap 요소 추가 및 제거

`heap.Pop` Heap에서 현재 최소(또는 최대 힙의 경우 최대) 요소를 가져올 수 있다. 이 요소도 Heap에서 제거되고 Heap 속성을 유지하도록 Heap이 재구성된다.

 

 

최솟값(1)이 제거되어 힙이 재구성된 것을 볼 수 있다.

 

 

 

 

 

요소 추가 및 제거는 모두 O(log(n)) 시간에 발생하므로 힙을 사용하는 것은 효율적으로 추가 및 제거할 수 있는 좋은 방법이다.

---

출처

Heap Implementation in Go | CodingDrills

Heap Implementation in Go | CodingDrills

Golang - Implementing Heap Data Structure (and Heap Sort) (sohamkamani.com)

Golang - Implementing Heap Data Structure (and Heap Sort)