/* 본 게시물은 참고자료를 토대로 작성되었습니다. */
/* 본 글은 개인적으로 공부한 내용을 정리한 글이므로 오류가 있을 수 있습니다. */
참고 자료
[BoostCourse] 자바로 구현하고 배우는 자료구조 - Heap : https://www.boostcourse.org/cs204
1. 힙이란?
힙은 '최댓값 및 최솟값을 찾아내는 연산'을 빠르게 하기 위해 고안된 '완전이진트리를 기반으로 한 자료구조'이다.
완전이진트리 조건
1. 마지막 레벨을 제외한 모든 노드가 채워져야한다.
2. 모든 노드들은 왼쪽부터 채워져야한다.
힙에는 최대 힙(max heap)과 최소 힙(min heap)이 있다. 부모 노드가 자식 노드보다 크면 최대 힙, 반대이면 최소 힙이다. 가장 큰 숫자가 뿌리에 있게 하려면 최대 힙, 가장 작은 숫자로부터 시작하려면 최소 힙을 사용하면 된다.
| n | level | height | log2(n+1) - 1 |
| 1 | 0 | 0 | 0 |
| 3 | 1 | 1 | 1 |
| 7 | 2 | 2 | 2 |
| 15 | 3 | 3 | 3 |
log2(n+1)−1 은 height와 일치하므로, 트리에 요소가 몇 개 있는지 알면 트리의 높이를 계산할 수 있다.
2. 힙 구현하기
[Stranger's Lab] 배열을 이용한 heap 구현 : https://st-lab.tistory.com/205#%EC%A0%84%EC%B2%B4
힙에 대해 자세히 알고 싶으면 위 링크를 들어가자.(강추) 앞으로 구현할 코드의 원리들도 논문급으로 잘 정리되어 있다.
Heap 클래스 / 부모, 자식 노드 메서드
완전이진트리로 배열에 index 1부터 데이터를 넣으면 다음과 같은 성질을 가진다.
1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2
위 성질을 이용해 기본적인 Heap 클래스에 부모, 자식 노드를 찾는 메서드를 코드로 구현해보자.
class Heap<E>(capacity: Int = DEFAULT_CAPACITY, comparator: Comparator<in E?>? = null) {
val array = arrayOfNulls<Object>(capacity)
var size = 0
// 받은 인덱스의 부모 노드 인덱스를 반환
private fun getParent(index: Int): Int {
return index / 2
}
// 받은 인덱스의 왼쪽 자식 노드 인덱스를 반환
private fun getLeftChild(index: Int): Int {
return index * 2
}
// 받은 인덱스의 오른쪽 자식 노드 인덱스를 반환
private fun getRightChild(index: Int): Int {
return index * 2 + 1
}
companion object {
private const val DEFAULT_CAPACITY = 10 // 기본 용량
}
}resize() 메서드 추가하기
배열 용량이 초과할 때 배열 용량을 증가시킨 새 배열에 기존 배열에 있던 값들을 복사하는 함수이다.
// 용량 초과 시 용량 증가하는 함수
private fun resize(newCapacity: Int) {
// 새로 만들 배열
val newArray = arrayOfNulls<Object>(newCapacity)
// 새 배열에 기존에 있던 배열의 요소들 복사
for (i in 1..size) {
newArray[i] = array[i]
}
array = newArray
}add() 메서드 추가하기
최대 힙이면 부모 노드가 자식 노드보다 커야 하고 최소 힙은 자식 노드가 부모 노드보다 커야 한다.
노드를 추가하는 과정은 다음과 같다.
1. 비어있는 공간에 노드를 추가한다.
2. 부모 노드보다 큰 숫자인지 확인하고 만약 그렇다면 두 노드를 바꾼다. (trickle up)
fun add(value: E) {
// 용량이 꽉 차있을 경우 용적을 두 배로 늘려준다.
if (size + 1 == array.size) {
resize(array.size * 2)
}
array[size+1] = value
trickleUp(size + 1, value as Comparable<E>) // 가장 마지막에 추가 되는 위치와 넣을 값(타겟)을 넘겨줌
size++ // 정상적으로 재배치가 끝나면 사이즈를 증가
}
private fun swap(from: Int, to: Int) {
val tmp: E = array[from] as E
array[from] = array[to]
array[to] = tmp
}
private fun trickleUp(idx: Int, target: Comparable<E>){
val parent = getParent(idx)
val parentVal = array[parent] as E
if (idx <= 1){
return
}
if (target > parentVal){
swap(idx, parent)
trickleUp(parent, target)
}
}remove() 메서드 추가하기
노드를 제거하는 메서드도 add() 메서드와 비슷하다.
1. 루트를 제거한다.
2. 트리의 마지막 요소를 루트에 넣어준다.
3. 루트에서 시작하여 두 자식 중 큰 노드와 바꿔주어 힙의 규칙을 만족하게 한다. (trickle down)
fun remove(): E{
val removeVal = array[1] as E
if (array[1] == null){
throw NoSuchElementException()
}
// swap(1,size--) -> heap Sort
array[1] = array[size]
array[size] = null
size--
trickleDown(1)
return removeVal
}
private fun trickleDown(parent: Int){
val left = getLeftChild(parent)
val right = getRightChild(parent)
// 마지막 노드가 왼쪽 자식 밖에 없을 때 왼쪽 자식이 클 때
if (left == size && (array[parent] as Comparable<E>) < (array[left] as E)){
swap(parent,left)
return
}
// 마지막에 오른쪽 자식이 클 때
if (right == size && (array[parent] as Comparable<E>) > (array[left] as E)){
swap(parent,right)
}
// 마지막에 부모가 클 때 (밑에 자식이 없을 때)
if (left > size || right > size)
return
// 왼쪽 자식이 클 때
if (array[left] as Comparable<E> > array[right] as E && array[parent] as Comparable<E> < array[left] as E) {
swap(parent, left);
trickleDown(left);
}
// 오른쪽 자식이 클 때
else if (array[parent] as Comparable<E> < array[right] as E){
swap(parent, right);
trickleDown(right);
}
}[응용] Comparable Comparator 를 이용한 객체 비교
*Comparable , Comparator 로 2가지 경우로 비교하도록 구현함. Comparable, Comparator 에 관한 내용이 궁금할 경우 다음 글을 참고 바람.
fun add(value: E) {
// 용량이 꽉 차있을 경우 용적을 두 배로 늘려준다.
if (size + 1 == array.size) {
resize(array.size * 2)
}
trickleUp(size + 1, value) // 가장 마지막에 추가 되는 위치와 넣을 값(타겟)을 넘겨줌
size++ // 정상적으로 재배치가 끝나면 사이즈를 증가
}
private fun trickleUp(idx: Int, target: E) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨줌
if (comparator != null) {
trickleUpComparator(idx, target, comparator)
} else {
trickleUpComparable(idx, target)
}
}
private fun trickleUpComparable(idx: Int, target: E) { // idx : 마지막 index, target : 추가할 노드
// root 노드보다 클 때까지만 탐색한다.
// 타겟노드가 비교 될 수 있도록 한 변수를 만든다.
var idx = idx
val comp = target as Comparable<E?>
while (idx > 1) {
val parent = getParent(idx) // 삽입노드의 부모노드 인덱스 구하기
val parentVal = array[parent]!! // 부모노드의 값
// 타겟 노드 값이 부모노드보다 작으면 반복문 종료
if (comp.compareTo(parentVal as E) <= 0) { // 최소 힙 구현 원할 시 >=0
break
}
/*
부모노드가 타겟노드보다 클 때
-> 현재 삽입 될 위치에 부모노드 값으로 교체하고
-> 타겟 노드의 위치를 부모노드의 위치로 변경한다.
*/
array[idx] = parentVal
idx = parent
}
// 최종적으로 삽입될 위치에 타겟 노드 값을 저장한다.
array[idx] = comp
}
private fun trickleUpComparator(idx: Int, target: E, comp: Comparator<in E?>) {
var idx = idx
while (idx > 1) {
val parent = getParent(idx)
val parentVal: Any = array[parent]!!
if (comp.compare(target, parentVal as E) <= 0) {
break
}
array[idx] = parentVal
idx = parent
}
array[idx] = target
} fun remove(): E {
if (array[1] == null) { // 만약 root가 비어있을경우 예외를 던지도록 함
throw NoSuchElementException()
}
val result = array[1] as E // 삭제된 요소를 반환하기 위한 임시 변수
val target = array[size] as E // 타겟이 될 요소
array[size] = null // 타겟 노드를 비운다.
// 삭제할 노드의 인덱스와 이후 재배치 할 타겟 노드를 넘겨준다.
trickleDown(1, target) // 루트 노드가 삭제되므로 1을 넘겨준다.
return result
}
private fun trickleDown(idx: Int, target: E) {
if (comparator != null) {
trickleDownComparator(idx, target, comparator)
} else {
trickleDownComparable(idx, target)
}
}
private fun trickleDownComparable(idx: Int, target: E) {
val comp = target as Comparable<E?>
array[idx] = null
size--
var parent = idx
var child: Int
while (getLeftChild(parent).also { child = it } <= size) {
val right = getRightChild(parent)
var childVal = array[child]!!
if (right <= size && (childVal as Comparable<E?>).compareTo(array[right] as E) > 0) {
child = right
childVal = array[child]!!
}
if (comp.compareTo(childVal as E) <= 0) {
break
}
array[parent] = childVal
parent = child
}
array[parent] = comp
if (array.size > DEFAULT_CAPACITY && size < array.size / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.size / 2))
}
}
private fun trickleDownComparator(idx: Int, target: E, comp: Comparator<in E?>) {
array[idx] = null // 삭제 할 인덱스의 노드를 삭제
size--
var parent = idx // 삭제노드부터 시작 할 부모를 가리키는 변수
var child: Int // 교환 될 자식을 가리키는 변수
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때 까지 반복
while (getLeftChild(parent).also { child = it } <= size) {
val right = getRightChild(parent) // 오른쪽 자식 인덱스
var childVal = array[child]!! // 왼쪽 자식의 값 (교환 될 값)
/*
* 오른쪽 자식 인덱스가 size를 넘지 않으면서
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 재배치 할 노드는 작은 자식과 비교해야하므로 child와 childVal을
* 오른쪽 자식으로 바꿔준다.
*/
if (right <= size && comp.compare(childVal as E, array[right] as E) > 0) {
child = right
childVal = array[child]!!
}
// 재배치 할 노드가 자식 노드보다 작을경우 반복문을 종료한다.
if (comp.compare(target, childVal as E) <= 0) {
break
}
/*
* 현재 부모 인덱스에 자식 노드 값을 대체해주고
* 부모 인덱스를 자식 인덱스로 교체
*/
array[parent] = childVal
parent = child
}
// 최종적으로 재배치 되는 위치에 타겟이 된 값을 넣어준다.
array[parent] = target
/*
* 용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
* 용적을 반으로 줄임(단, 최소용적보단 커야함)
*/
if (array.size > DEFAULT_CAPACITY && size < array.size / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.size / 2))
}
}
}Heap 구현하면서 생긴 의문점(제네릭에 관하여 2021-10-18)
class Heap<E> 내부에 있는 array 에 대해서 arrayOfNulls<Any> 대신 arrayOfNulls<E> 를 사용할 수 있으면 좋을텐데 불가능했다. 그래서 array 내부에 있는 요소들에 대해 비교할 때마다 형변환을 했는데 이러면 generic 의 의미가 없다는 생각이 든다.. Array<E> 를 생성할 수 있는 방법이 없을까?
반응형
