저작권 안내
- 책 또는 웹사이트의 내용을 복제하여 다른 곳에 게시하는 것을 금지합니다.
- 책 또는 웹사이트의 내용을 발췌, 요약하여 강의 자료, 발표 자료, 블로그 포스팅 등으로 만드는 것을 금지합니다.
컨테이너 사용하기
이재홍 http://www.pyrasis.com 2014.12.17 ~ 2015.02.07
힙 사용하기
다음은 container/heap 함수에서 제공하는 힙 함수입니다.
- func Init(h Interface): 힙 초기화
- func Push(h Interface, x interface{}): 힙에 데이터 추가
이제 힙을 사용해보겠습니다.
package main
import (
"container/heap"
"fmt"
)
type MinHeap []int // 힙을 int 슬라이스로 정의
func (h MinHeap) Len() int {
return len(h) // 슬라이스의 길이를 구함
}
func (h MinHeap) Less(i, j int) bool {
r := h[i] < h[j] // 대소관계 판단
fmt.Printf("Less %d < %d %t\n", h[i], h[j], r)
return r
}
func (h MinHeap) Swap(i, j int) {
fmt.Printf("Swap %d %d\n", h[i], h[j])
h[i], h[j] = h[j], h[i] // 값의 위치를 바꿈
}
func (h *MinHeap) Push(x interface{}) {
fmt.Println("Push", x)
*h = append(*h, x.(int)) // 맨 마지막에 값 추가
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1] // 슬라이스의 맨 마지막 값을 가져옴
*h = old[0 : n-1] // 맨 마지막 값을 제외한 슬라이스를 다시 저장
return x
}
func main() {
data := new(MinHeap) // 힙 생성
heap.Init(data) // 힙 초기화
heap.Push(data, 5) // 힙에 데이터 추가
heap.Push(data, 2)
heap.Push(data, 7)
heap.Push(data, 3)
fmt.Println(data, "최솟값 : ", (*data)[0])
}
힙은 완전 이진 트리(Complete binary tree)를 사용한 자료구조이며 두 가지 종류가 있습니다.
- 최대 힙: 부모 노드의 값이 자식 노드의 값 보다 큰 힙
- 최소 힙: 부모 노드의 값이 자식 노드의 값 보다 작은 힙
예제에서는 최소 힙을 구현해보았습니다. 리스트 같은 자료구조와는 달리 힙은 heap.Interface를 구현해주어야 합니다.
먼저 힙의 데이터 타입을 정의합니다. 여기서는 간단하게 정수형 슬라이스로 정의했습니다.
type MinHeap []int // 힙을 int 슬라이스로 정의
데이터를 넣는 Push 메서드와 데이터를 꺼내는 Pop 메서드를 정의합니다.
func (h *MinHeap) Push(x interface{}) {
fmt.Println("Push", x)
*h = append(*h, x.(int)) // 맨 마지막에 값 추가
}
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1] // 슬라이스의 맨 마지막 값을 가져옴
*h = old[0 : n-1] // 맨 마지막 값을 제외한 슬라이스를 다시 저장
return x
}
Push 메서드는 슬라이스 마지막에 값을 추가하며 Pop 메서드는 슬라이스의 맨 마지막 값을 가져옵니다. 여기서는 old[n-1]로 맨 마지막 값을 가져온 뒤 *h = old[0 : n-1]처럼 맨 마지막 값을 제외한 슬라이스를 다시 데이터에 저장합니다.
이제 정렬(sort.Interface)을 구현합니다(sort.Interface 인터페이스는 heap.Interface 인터페이스 안에 임베딩되어 있습니다).
func (h MinHeap) Len() int {
return len(h) // 슬라이스의 길이를 구함
}
func (h MinHeap) Less(i, j int) bool {
r := h[i] < h[j] // 대소관계 판단
fmt.Printf("Less %d < %d %t\n", h[i], h[j], r)
return r
}
func (h MinHeap) Swap(i, j int) {
fmt.Printf("Swap %d %d\n", h[i], h[j])
h[i], h[j] = h[j], h[i] // 값의 위치를 바꿈
}
- Len: 힙의 길이를 구하는 함수입니다. 슬라이스이므로
len함수를 사용하여 길이를 구합니다. - Less, Swap: 기존의 값(j)과 새로 들어온 값(i)을 비교하여 새로 들어온 값이 크면 그대로 두고, 새로 들어온 값이 작으면 기존 값과 교체합니다. 즉 부모 노드보다 자식 노드의 값이 크면 그대로 두고, 부모 노드보다 자식 노드가 작으면 서로 값을 바꿉니다(이 식을 반대로 하면 최대 힙이 됩니다). 값을 추가할 때마다 이 작업이 반복됩니다.
결과를 출력해보면 다음과 같이 heap.Push 함수로 값을 넣을 때마다 정렬이 됩니다.
실행 결과
Push 5
Push 2
Less 2 < 5 true
Swap 5 2
Push 7
Less 7 < 2 false
Push 3
Less 3 < 5 true
Swap 5 3
Less 3 < 2 false
&[2 3 7 5] 최솟값 : 2
실행 과정을 그림으로 표현하면 다음과 같습니다.
그림 55-2 최소 힙 정렬 과정
Kubernetes
저작권 안내
이 웹사이트에 게시된 모든 글의 무단 복제 및 도용을 금지합니다.- 블로그, 게시판 등에 퍼가는 것을 금지합니다.
- 비공개 포스트에 퍼가는 것을 금지합니다.
- 글 내용, 그림을 발췌 및 요약하는 것을 금지합니다.
- 링크 및 SNS 공유는 허용합니다.