컨테이너 사용하기


이재홍 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 최소 힙 정렬 과정


저작권 안내

이 웹사이트에 게시된 모든 글의 무단 복제 및 도용을 금지합니다.
  • 블로그, 게시판 등에 퍼가는 것을 금지합니다.
  • 비공개 포스트에 퍼가는 것을 금지합니다.
  • 글 내용, 그림을 발췌 및 요약하는 것을 금지합니다.
  • 링크 및 SNS 공유는 허용합니다.

Published

01 June 2015