자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기
자료구조 관련 목록 링크 펼치기
0. 자바 컬렉션 프레임워크 (Java Collections Framework)
3. 단일 연결리스트 (Singly LinkedList)
4. 이중 연결리스트 (Doubly LinkedList)
6. 스택 (Stack)
11. 연결리스트 덱 (LinkedList Deque)
12. 배열 힙 (Heap) - [현재 페이지]
15. 해시 셋 (Hash Set)
17. 이진 탐색 트리 (Binary Search Tree)
- Heap (using array)
오늘은 다른 자료구조 포스팅과는 다르게 Heap에 대해서 따로 배워보고자 한다.
그 이유는 앞으로 구현할 '우선순위 큐'가 바로 힙 자료구조를 이용하여 구현되기 때문이다. 그렇기 때문에 이번에는 Heap 자료구조에 대해 기본적으로 어떻게 구현되고, 어떻게 동작하는지를 알아보고 그 다음 포스팅에서 우선순위 큐를 구현하고자 한다.
또한 단순히 int 형 같이 primitive 타입으로만 구현하는 것이 아닌 객체타입도 쓸 수 있도록 구현할 것이기 때문에 기본적인 제네릭에 대해서도 이해하고 가야한다.
제네릭에 대해 간단하게 알아보고자 한다면 아래 글을 참고하시길 바란다.
그럼 일단 Heap(힙)이란 무엇인가를 알아보자.
힙은 '최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조'다.
위 문장에서 중요한 키워드 3가지가 있다. 바로 '최솟값 또는 최댓값' , '빠르게', '완전이진트리' 이다. 일단 이 키워드를 이해하기 위해서는 '완전이진트리'를 이해해야 한다.
기본적으로 트리(tree)가 무엇인지 잠깐 보고가자.
위와같은 구조를 Tree 구조라고 한다. 위 그림을 거꾸로 보면 나무같이 생겨서 tree구조라고 한다. 여기서 몇 가지 알아야 할 것이 있다. 이 부분만 짚자면 아래와 같다.
부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)
자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)
루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다.
단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.
내부 노드(internal node) : 단말 노드가 아닌 노드
형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)
깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)
레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)
차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} )
이 정도만 알고 있으면 된다.
그리고 위 트리 구조에서 특정한 형태로 제한을 하게 되는데, 모든 노드의 최대 차수를 2로 제한한 것이다. 조금 쉽게 말하자면 각 노드는 자식노드를 최대 2개까지밖에 못갖는 것이다. 이를 '이진 트리(Binary Tree)'라고 한다.
위의 이미지에서는 B노드가 차수가 3이므로 이진트리가 아니다. 즉, 이진트리의 경우 다음과 같은 형태를 띈다.
그럼 이제 마지막으로 '완전 이진 트리(complete binary tree)' 에서 '완전'이라는 것은 무엇인지 알아보아야 한다.
'완전 이진 트리'란 먼저 정의하자면 '마지막 레벨'을 제외한 모든 노드가 채워져있으면서 모든 노드(=사실상 마지막 레벨의 노드들)가 왼쪽부터 채워져있어야 한다.
즉, 완전 이진 트리는 이진 트리에서 두 가지 조건을 더 만족해야 하는 것이다.
1. 마지막 레벨을 제외한 모든 노드가 채워져있어야함
2. 모든 노드들은 왼쪽부터 채워져있어야함
그리고 완전 이진 트리에서 한 가지 조건만 더 추가하면 '포화 이진 트리(perfect binary tree)'가 된다. 바로 '마지막 레벨을 제외한 모든 노드는 두 개의 자식노드를 갖는다'라는 조건이다.
이렇게 이진 트리에 대해 개념을 살펴보았다.
그럼 힙(Heap)은 어떻게 구현되냐? 이 부분이 가장 큰 문제일 것이다. 즉, 최댓값 혹은 최솟값을 어떻게 빠르게 찾아낼 수 있는가를 고민해야한다는 것이다.
예로들어보자.
여러분이 어떤 리스트에 값을 넣었다가 빼낼려고 할 때, 우선순위가 높은 것 부터 빼내려고 한다면 대개 정렬을 떠올리게 된다.
쉽게 생각해서 숫자가 낮을 수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때 마다 이미 리스트에 있던 원소들과 비교를 하고 정렬을 해야한다.
문제는 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 다음과 같은 조건을 붙였다.
'부모 노드는 항상 자식 노드보다 우선순위가 높다.'
즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식노드보다 항상 우선순위가 앞선다는 조건만 만족시키며 완전이진트리 형태로 채워나가는 것이다.
이를 조금만 돌려서 생각해보면 루트 노드(root node)는 항상 우선순위가 높은 노드라는 것이다. 이러한 원리로 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다는 장점(시간복잡도 : O(1))과 함께 삽입 삭제 연산시에도 부모노드가 자식노드보다 우선순위만 높으면 되므로 결국 트리의 깊이만큼만 비교를 하면 되기 때문에 O(logN) 의 시간복잡도를 갖아 매우 빠르게 수행할 수 있다.
그리고 위 이미지에서도 볼 수 있지만 부모노드와 자식노드간의 관계만 신경쓰면 되기 때문에 형제 간 우선순위는 고려되지 않는다.
이러한 정렬 상태를 흔히 '반 정렬 상태' 혹은 '느슨한 정렬 상태' , '약한 힙(weak heap)'이라고도 불린다.
그럼 이런 질문이 나올 수 있다. "왜 형제간의 대소비교가 필요 없다는 거죠?"
우선순위가 높은 순서대로 뽑는 것이 포인트다. 즉, 원소를 넣을 때도 우선순위가 높은 순서대로 나올 수 있도록 유지가 되야하고 뽑을 때 또한 우선순위가 높은 순서 차례대로 나오기만 하면 된다.
말로하면 어려울 수도 있으나 구현부분을 보면 바로 이해할 수 있을 것이다.
- Heap의 종류
앞서 힙은 우선순위가 높은 순서대로 나온다고 했다. 이 말은 여러분이 어떻게 우선순위를 매기냐에 따라 달라지겠지만, 기본적으로 정수, 문자, 문자열 같은 경우 언어에서 지원하는 기본 정렬 기준들이 있다.
예로들어 정수나 문자의 경우 낮은 값이 높은 값보다 우선한다.
우리가 예로 {3, 1, 6, 4} 를 정렬한다고 하면 낮은 순서대로 {1, 3, 4, 6} 이렇게 정렬하게 된다. 이렇게 정렬되는 순서, 즉 기본적으로 어떤 것을 우선순위가 높다고 할지에 따라 두 가지로 나뉜다.
최소 힙 : 부모 노드의 값(key 값) ≤ 자식 노드의 값(key 값)
최대 힙 : 부모 노드의 값(key 값) ≥ 자식 노드의 값(key 값)
이렇게 두 가지로 나뉜다.
다만, 여기서 가장 기본으로 우선순위를 뽑는다고 하면 보통 '오름차순'을 생각하기도 하고 많은 언어들도 오름차순을 기본으로 하기 때문에 오늘을 '최소 힙'을 구현해볼 것이다. (최대 힙의 경우 비교연산자만 바꿔주면 되기 때문에 어떤 것을 구현하더라도 크게 문제는 없다.)
그럼 위의 트리 구조를 어떻게 구현할 것인가?
가장 표준적으로 구현되는 방식은 '배열' 이다. 물론 연결리스트로도 구현이 가능하긴 하지만, 문제는 특정 노드의 '검색', '이동' 과정이 조금 더 번거롭기 때문이다.
배열의 경우는 특정 인덱스에 바로 접근할 수가 있기 때문에 좀 더 효율적이기도 하다.
배열로 구현하게 되면 특징 및 장점들이 있다. 일단 아래 그림을 한 번 봐보도록 하자.
[특징]
1. 구현의 용이함을 위해 시작 인덱스(root)는 1 부터 시작한다.
2. 각 노드와 대응되는 배열의 인덱스는 '불변한다'
위 특징을 기준으로 각 인덱스별로 채워넣으면 특이한 성질이 나오는데 이는 다음과 같다.
[성질]
1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2
위 세개의 법칙은 절대 변하지 않는다.
예로들어 index 3 의 왼쪽 자식 노드를 찾고 싶다면 3 × 2를 해주면 된다. 즉 index 6 이 index 3 의 자식 노드라는 것이다.
반대로 index 5의 부모 노드를 찾고 싶다면 5 / 2 를 해주면 된다.(몫만 취함) 그러면 2 이므로 index 2가 index 5의 부모노드라는 것이다.
그러면 위 설명을 바탕으로 한 번 구현해보도록 해보자.
- Heap 구현
앞서 말했지만, 일단 기본적으로 최소 힙(Min Heap)을 기준으로 설명드리도록 하겠다. 최대 힙 또한 원리가 크게 다른 건 아니라 만약 최대힙을 구현하고 싶은 경우 비교 연산만 반대로 해주면 된다.
[구현 바로가기]
<필수 목록>
◦ size, peek, isEmpty ,toArray 메소드 구현
◦ 전체 코드
[Heap 클래스 및 생성자 구성하기]
이 번에 구현 할 힙은 배열 기반으로 구현된다는 것을 알았으면 한다. Heap 이라는 이름으로 생성한다.
[Heap.java]
import java.util.Comparator;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
private int size; // 요소 개수
private Object[] array; // 요소를 담을 배열
// 생성자 Type 1 (초기 공간 할당 X)
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
// 생성자 Type 2 (초기 공간 할당 O)
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
// 받은 인덱스의 부모 노드 인덱스를 반환
private int getParent(int index) {
return index / 2;
}
// 받은 인덱스의 왼쪽 자식 노드 인덱스를 반환
private int getLeftChild(int index) {
return index * 2;
}
// 받은 인덱스의 오른쪽 자식 노드 인덱스를 반환
private int getRightChild(int index) {
return index * 2 + 1;
}
}
변수부터 먼저 차례대로 설명해주도록 하겠다.
comparator : 여러분들이 객체를 정렬하고자 할 때, 혹은 임의의 순서로 정렬하고 싶을 때 Comparator 를 파라미터로 받아 설정할 수 있도록 한 변수다.
DEFAULT_CAPACITY : 배열의 기본 및 최소 용적이다. 한마디로 요소를 담을 배열의 크기를 의미한다. 배열을 동적으로 관리 할 때 최소 크기가 10 미만으로 내려가지 않기 위한 변수다. 그리고 요소의 개수랑은 다른 의미이므로 이 점 헷갈리지 말자.
size : 배열에 담긴 요소(원소)의 개수 변수
array : 요소를 담을 배열이다.
그리고 생성자는 크게 4가지로 나누었다.
먼저 데이터(요소)의 개수를 예상할 수 있어 배열의 크기(용적)를 최적으로 하고 싶을 때 초기에 생성할 배열의 크기를 설정 해줄 수 있도록 만든 방법과 사용자가 정렬 방법을 따로 넘겨주고자 할 때 쓸 수 있도록 Comparator을 받는 방법을 조합하여 4가지로 나누었다.
그리고 힙 설명에서 힙을 배열로 구현하게 될 때의 성질에 관해 배웠다.
[성질]
1. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2
2. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 × 2 + 1
3. 부모 노드 인덱스 = 자식 노드 인덱스 / 2
위 세 가지 성질을 이용하기 위해 각각 부모 또는 자식의 인덱스를 반환해주는 메소드를 생성해주었다.
[resize 메소드 구현]
모든 자료구조는 기본적으로 동적으로 만들 수 있어야 한다.
만약 배열에 요소들이 모두 차면 배열의 크기를 늘려야하고, 만약 요소가 배열 용적에 비해 현저히 적으면 낭비되는 메모리가 크므로 적절히 줄여줄 수 있어야 한다.
그럴 때 배열의 크기를 재조정하기 위해 쓰는 메소드다.
/**
* @param newCapacity 새로운 용적 크기
*/
private void resize(int newCapacity) {
// 새로 만들 배열
Object[] newArray = new Object[newCapacity];
// 새 배열에 기존에 있던 배열의 요소들을 모두 복사해준다.
for(int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null로 처리한 뒤,
* 새 배열을 연결해준다.
*/
this.array = null;
this.array = newArray;
}
위 과정대로 새 배열을 생성하고 기존에 있던 배열의 요소들을 복사해준 뒤, 새 배열을 가리키도록 새로 연결해주면 된다.
이 부분 자체는 어려울 건 없을 것이다.
[add 메소드 구현]
이제 본격적으로 Heap에 데이터를 추가할 수 있도록 해보자.
Heap의 삽입은 크게 두 가지로 나뉜다.
1. 사용자가 Comparator을 사용하여 정렬 방법을 Heap 생성단계에서 넘겨받은 경우 (comparator가 null이 아닌 경우)
2. 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우 (comparator가 null인 경우)
이 두 가지로 나누어 봐야한다.
기본적으로 Heap에서 원소가 추가되는 과정을 다음 이미지와 같다.
즉, 배열의 마지막 부분에 원소를 넣고 부모노드를 찾아가면서 부모 노드가 삽입 노드보다 작을 때 까지 요소를 교환해가면서 올라간다. 위와 같은 과정을 흔히 위로 올라가면서 선별한다고 하여 sift-up (상향 선별) 이라고도 불린다.
즉, 값을 추가 할 때는 size + 1 위치에 새로운 값을 추가하고 상향 선별 과정을 거쳐 '재배치'를 해준다고 생각하면 된다.
이 때, 재배치 되는 노드를 위 분홍색 노드 즉, 타겟노드(target)라고 생각하면 된다.
그럼 위 과정을 코드로 옮겨보자.
public void add(E value) {
// 배열 용적이 꽉 차있을 경우 용적을 두 배로 늘려준다.
if(size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value); // 가장 마지막에 추가 되는 위치와 넣을 값(타겟)을 넘겨줌
size++; // 정상적으로 재배치가 끝나면 사이즈를 증가
}
// 상향 선별
/**
* @param idx 추가할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftUp(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftUpComparator(idx, target, comparator);
}
else {
siftUpComparable(idx, target);
}
}
// Comparator을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
// root노드보다 클 때까지만 탐색한다.
while(idx > 1) {
int parent = getParent(idx); // 삽입노드의 부모노드 인덱스 구하기
Object parentVal = array[parent]; // 부모노드의 값
// 타겟 노드 값이 부모노드보다 크면 반복문 종료
if(comp.compare(target, (E) parentVal) >= 0) {
break;
}
/*
* 부모노드가 타겟노드보다 크므로
* 현재 삽입 될 위치에 부모노드 값으로 교체해주고
* 타겟 노드의 위치를 부모노드의 위치로 변경해준다.
*/
array[idx] = parentVal;
idx = parent;
}
// 최종적으로 삽입될 위치에 타겟 노드 값을 저장해준다.
array[idx] = target;
}
// 삽입 할 객체의 Comparable을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
// 타겟노드가 비교 될 수 있도록 한 변수를 만든다.
Comparable<? super E> comp = (Comparable<? super E>) target;
while(idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if(comp.compareTo((E)parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}
주석으로 설명을 해 놓았지만, 다시 한 번 글로 설명을 하자면 이렇다.
일단 요소를 추가하기 전에 추가 할 공간이 있는지를 검사해야 한다. 만약 배열의 길이(용적)가 10이고, 요소의 개수인 size가 9일 경우 배열의 마지막 인덱스까지 꽉 찼다는 의미다. (힙은 index 1부터 채우므로)
그렇기에 용적의 크기를 2배로 늘려 준 뒤, siftUp 메소드를 호출 해준다.
그 다음 앞서 말했던 Comparator로 넘겨받은 것이 있는지, 없는지에 따라 Comparator가 있을 경우 compre()을, 없을 경우 compareTo()를 사용하여 요소를 비교해야 하므로 검사를 한 뒤 각각의 siftUp 메소드로 넘어가 재배치 작업을 해준다.
위와같이 추가해보다보면 알겠지만 결국 '마지막 삽입 되는 인덱스'부터 부모노드를 비교하면서 올라가기 때문에 항상 완전 이진 트리를 만족하면서, 부모노드는 자식노드보다 우선순위가 높다는 것 또한 침해받지 않는다.
그리고 만약 최대힙을 구현하고 싶은 경우 compare 혹은 compareTo에서의 >= 0 비교연산자를 <= 로 바꿔주면 된다.
[add 메소드 묶어보기]
public void add(E value) {
if(size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value);
size++;
}
/**
* @param idx 추가할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftUp(int idx, E target) {
if(comparator != null) {
siftUpComparator(idx, target, comparator);
}
else {
siftUpComparable(idx, target);
}
}
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
while(idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if(comp.compare(target, (E) parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = target;
}
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
Comparable<? super E> comp = (Comparable<? super E>) target;
while(idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if(comp.compareTo((E)parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}
[remove 메소드 구현]
그럼 삭제는 어떻게 구현해야할까? 간단한 해답은 add와 정반대로 하면 된다.
add의 경우 맨 마지막 노드에 추가하고 부모노드와 비교하면서 자리를 찾아갔다. 이를 거꾸로 하면 삭제연산의 경우 root에 있는 노드를 삭제하고, 마지막에 위치해있던 노드를 root Node로 가져와 add와는 반대로 자식노드가 재배치하려는 노드보다 크거나 자식노드가 없을 때 까지 자신의 위치를 찾아가면 된다.
이렇게 글로 쓰면 이해가 쉽게 되지 않을테니 한 번 그림으로 보자.
위와 같이 마지막 노드를 root노드로 가져온 뒤, 자식 노드와 비교하면서 자리를 찾아가면 된다. 즉, 비교 대상이 되는 '분홍색 노드'는 타겟(target)이 되는 것이다. 이 타겟을 다른 노드와 비교하면서 타겟 노드가 배치 될 자리를 찾아가야 한다.
중요한 점은 왼쪽 자식 노드와 오른쪽 자식 노드 중 '작은 값을 가진 노드'랑 재배치 할 노드와 비교해야한다.
그래야 최소 힙을 만족시킬 수 있다. 만약 반대로 된다면 첫 비교 교환 단계에서 35가 root노드에 배치되어버리는데, 이는 왼쪽 자식노드인 10보다 큰 값을 갖게 되면서 최소힙을 만족하지 못한다.
이렇게 아래로 내려가면서 재배치 하는 과정을 이러한 과정을 sift-down (하향 선별)이라고도 한다.
그리고 삽입과정과 마찬가지로 Comparator을 쓰느냐, Comparable을 쓰느냐를 나누면서 만들겠다.
@SuppressWarnings("unchecked")
public E remove() {
if(array[1] == null) { // 만약 root가 비어있을경우 예외를 던지도록 함
throw new NoSuchElementException();
}
E result = (E) array[1]; // 삭제된 요소를 반환하기 위한 임시 변수
E target; // 타겟이 될 요소
if(size == 1) {
target = null;
}
else {
target = (E) array[size];
}
array[size] = null; // 타겟 노드를 비운다.
// 삭제할 노드의 인덱스와 이후 재배치 할 타겟 노드를 넘겨준다.
siftDown(1, target); // 루트 노드가 삭제되므로 1을 넘겨준다.
return result;
}
/**
* @param idx 삭제할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftDown(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftDownComparator(idx, target, comparator);
}
else {
siftDownComparable(idx, target);
}
}
// Comparator을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null; // 삭제 할 인덱스의 노드를 삭제
size--;
int parent = idx; // 삭제노드부터 시작 할 부모를 가리키는 변수
int child; // 교환 될 자식을 가리키는 변수
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때 까지 반복
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent); // 오른쪽 자식 인덱스
Object childVal = array[child]; // 왼쪽 자식의 값 (교환 될 값)
/*
* 오른쪽 자식 인덱스가 size를 넘지 않으면서
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 재배치 할 노드는 작은 자식과 비교해야하므로 child와 childVal을
* 오른쪽 자식으로 바꿔준다.
*/
if(right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
// 재배치 할 노드가 자식 노드보다 작을경우 반복문을 종료한다.
if(comp.compare(target ,(E) childVal) <= 0){
break;
}
/*
* 현재 부모 인덱스에 자식 노드 값을 대체해주고
* 부모 인덱스를 자식 인덱스로 교체
*/
array[parent] = childVal;
parent = child;
}
// 최종적으로 재배치 되는 위치에 타겟이 된 값을 넣어준다.
array[parent] = target;
/*
* 용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
* 용적을 반으로 줄임(단, 최소용적보단 커야함)
*/
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
// Comparable을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
size--;
int parent = idx;
int child;
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if(right <= size && ((Comparable<? super E>)childVal).compareTo((E)array[right]) > 0) {
child = right;
childVal = array[child];
}
if(comp.compareTo((E) childVal) <= 0){
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = comp;
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
삭제 과정 위와 같이 하면 된다.
여기서 중요한 점은 size가 1일 때 요소를 삭제하면 이제 힙에는 모든 원소가 삭제되어야 한다. 이 때, sift-down에서 대체되는 타겟 요소는 target이란 변수가 대체되는 것이기 때문에, size=1일 때 null 값이 아닌 target = (E) array[size]; 를 해버리면 삭제된 요소가 다시 부활해버리는 불상사가 발생한다. 그러니 이 점 유의하여 size = 1 일 때는 target = null 로 하여야 한다.
그리고 마찬가지로 최대 힙을 구현하고 싶다면 비교과정을 반대로 해주면 된다.
또한, 배열의 요소가 하나도 없는데 remove() 하려는 경우 NoSuchElementException 을 발생시키기로 했다.
[remove 메소드 묶어보기]
@SuppressWarnings("unchecked")
public E remove() {
if(array[1] == null) {
throw new NoSuchElementException();
}
E result = (E) array[1];
E target;
if(size == 1) {
target = null;
}
else {
target = (E) array[size];
}
array[size] = null;
siftDown(1, target);
return result;
}
private void siftDown(int idx, E target) {
if(comparator != null) {
siftDownComparator(idx, target, comparator);
}
else {
siftDownComparable(idx, target);
}
}
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null;
size--;
int parent = idx;
int child;
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if(right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
if(comp.compare(target ,(E) childVal) <= 0){
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = target;
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
size--;
int parent = idx;
int child;
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if(right <= size && ((Comparable<? super E>)childVal).compareTo((E)array[right]) > 0) {
child = right;
childVal = array[child];
}
if(comp.compareTo((E) childVal) <= 0){
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = comp;
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
[size, peek, isEmpty, toArray 메소드 구현]
현재 Heap에 저장 된 요소의 개수를 알고 싶을 때 size값을 리턴하기 위한 메소드로 size()를 하나 만들고, 또한 가장 우선순위가 높은 원소인 루트 노드의 값만 확인하고 싶을 때 쓰는 메소드를 위해 peek() 메소드를 만들 것이다. 데이터를 삭제하지 않고 확인만 하고싶을 때 쓰는 것이 peek() 메소드다. 한마디로 remove() 메소드에서 삭제과정만 없는 것이 peek() 이다.
그리고 의외로 자주 쓰이는 현재 힙(Heap)에 요소가 아무 것도 없는 경우를 판별하기 위한 메소드도 하나 만들어주자. 이 때 힙에 아무 요소가 없다는 것은 size 가 0이라는 소리이므로 size == 0 인지를 반환해주면 된다.
마지막으로 toArray로 현재 Heap의 배열에 요소가 어떻게 배치되어있는지 볼 수 있도록 아주 간단하게 구현해볼 것이다.
size, peek, isEmpty, toArray 메소드
public int size() {
return this.size;
}
@SuppressWarnings("unchecked")
public E peek() {
if(array[1] == null) {
throw new NoSuchElementException();
}
return (E)array[1];
}
public boolean isEmpty() {
return size == 0;
}
public Object[] toArray() {
return Arrays.copyOf(array, size + 1);
}
참고로 peek() 또한 데이터가 비어있는 경우를 고려하도록 해주자.
[size, peek, isEmpty, toArray 메소드 묶어보기]
public int size() {
return this.size;
}
@SuppressWarnings("unchecked")
public E peek() {
if(array[1] == null) {
throw new NoSuchElementException();
}
return (E)array[1];
}
public boolean isEmpty() {
return size == 0;
}
public Object[] toArray() {
return Arrays.copyOf(array, size + 1);
}
- 전체 코드
import java.util.Comparator;
import java.util.NoSuchElementException;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_CAPACITY = 10; // 최소(기본) 용적 크기
private int size; // 요소 개수
private Object[] array; // 요소를 담을 배열
// 생성자 Type 1 (초기 공간 할당 X)
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
// 받은 인덱스의 부모 노드 인덱스를 반환
private int getParent(int index) {
return index / 2;
}
// 받은 인덱스의 왼쪽 자식 노드 인덱스를 반환
private int getLeftChild(int index) {
return index * 2;
}
// 받은 인덱스의 오른쪽 자식 노드 인덱스를 반환
private int getRightChild(int index) {
return index * 2 + 1;
}
// 생성자 Type 2 (초기 공간 할당 O)
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
/**
* @param newCapacity 새로운 용적 크기
*/
private void resize(int newCapacity) {
// 새로 만들 배열
Object[] newArray = new Object[newCapacity];
// 새 배열에 기존에 있던 배열의 요소들을 모두 복사해준다.
for(int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
/*
* 현재 배열은 GC 처리를 위해 null로 처리한 뒤,
* 새 배열을 연결해준다.
*/
this.array = null;
this.array = newArray;
}
public void add(E value) {
// 배열 용적이 꽉 차있을 경우 용적을 두 배로 늘려준다.
if(size + 1 == array.length) {
resize(array.length * 2);
}
siftUp(size + 1, value); // 가장 마지막에 추가 되는 위치와 넣을 값(타겟)을 넘겨줌
size++; // 정상적으로 재배치가 끝나면 사이즈를 증가
}
// 상향 선별
/**
* @param idx 추가할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftUp(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftUpComparator(idx, target, comparator);
}
else {
siftUpComparable(idx, target);
}
}
// Comparator을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparator(int idx, E target, Comparator<? super E> comp) {
// root노드보다 클 때까지만 탐색한다.
while(idx > 1) {
int parent = getParent(idx); // 삽입노드의 부모노드 인덱스 구하기
Object parentVal = array[parent]; // 부모노드의 값
// 타겟 노드 값이 부모노드보다 크면 반복문 종료
if(comp.compare(target, (E) parentVal) >= 0) {
break;
}
/*
* 부모노드가 타겟노드보다 크므로
* 현재 삽입 될 위치에 부모노드 값으로 교체해주고
* 타겟 노드의 위치를 부모노드의 위치로 변경해준다.
*/
array[idx] = parentVal;
idx = parent;
}
// 최종적으로 삽입될 위치에 타겟 노드 값을 저장해준다.
array[idx] = target;
}
// 삽입 할 객체의 Comparable을 이용한 sift-up
@SuppressWarnings("unchecked")
private void siftUpComparable(int idx, E target) {
// 타겟노드가 비교 될 수 있도록 한 변수를 만든다.
Comparable<? super E> comp = (Comparable<? super E>) target;
while(idx > 1) {
int parent = getParent(idx);
Object parentVal = array[parent];
if(comp.compareTo((E)parentVal) >= 0) {
break;
}
array[idx] = parentVal;
idx = parent;
}
array[idx] = comp;
}
@SuppressWarnings("unchecked")
public E remove() {
if(array[1] == null) { // 만약 root가 비어있을경우 예외를 던지도록 함
throw new NoSuchElementException();
}
E result = (E) array[1]; // 삭제된 요소를 반환하기 위한 임시 변수
E target; // 타겟이 될 요소
if(size == 1) {
target = null;
}
else {
target = (E) array[size];
}
array[size] = null; // 타겟 노드를 비운다.
// 삭제할 노드의 인덱스와 이후 재배치 할 타겟 노드를 넘겨준다.
siftDown(1, target); // 루트 노드가 삭제되므로 1을 넘겨준다.
return result;
}
/**
* @param idx 삭제할 노드의 인덱스
* @param target 재배치 할 노드
*/
private void siftDown(int idx, E target) {
// comparator가 존재할 경우 comparator 을 인자로 넘겨준다.
if(comparator != null) {
siftDownComparator(idx, target, comparator);
}
else {
siftDownComparable(idx, target);
}
}
// Comparator을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparator(int idx, E target, Comparator<? super E> comp) {
array[idx] = null; // 삭제 할 인덱스의 노드를 삭제
size--;
int parent = idx; // 삭제노드부터 시작 할 부모를 가리키는 변수
int child; // 교환 될 자식을 가리키는 변수
// 왼쪽 자식 노드의 인덱스가 요소의 개수보다 작을 때 까지 반복
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent); // 오른쪽 자식 인덱스
Object childVal = array[child]; // 왼쪽 자식의 값 (교환 될 값)
/*
* 오른쪽 자식 인덱스가 size를 넘지 않으면서
* 왼쪽 자식이 오른쪽 자식보다 큰 경우
* 재배치 할 노드는 작은 자식과 비교해야하므로 child와 childVal을
* 오른쪽 자식으로 바꿔준다.
*/
if(right <= size && comp.compare((E) childVal, (E) array[right]) > 0) {
child = right;
childVal = array[child];
}
// 재배치 할 노드가 자식 노드보다 작을경우 반복문을 종료한다.
if(comp.compare(target ,(E) childVal) <= 0){
break;
}
/*
* 현재 부모 인덱스에 자식 노드 값을 대체해주고
* 부모 인덱스를 자식 인덱스로 교체
*/
array[parent] = childVal;
parent = child;
}
// 최종적으로 재배치 되는 위치에 타겟이 된 값을 넣어준다.
array[parent] = target;
/*
* 용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
* 용적을 반으로 줄임(단, 최소용적보단 커야함)
*/
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
// Comparable을 이용한 sift-down
@SuppressWarnings("unchecked")
private void siftDownComparable(int idx, E target) {
Comparable<? super E> comp = (Comparable<? super E>) target;
array[idx] = null;
size--;
int parent = idx;
int child;
while((child = getLeftChild(parent)) <= size) {
int right = getRightChild(parent);
Object childVal = array[child];
if(right <= size && ((Comparable<? super E>)childVal).compareTo((E)array[right]) > 0) {
child = right;
childVal = array[child];
}
if(comp.compareTo((E) childVal) <= 0){
break;
}
array[parent] = childVal;
parent = child;
}
array[parent] = comp;
if(array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
public int size() {
return this.size;
}
@SuppressWarnings("unchecked")
public E peek() {
if(array[1] == null) {
throw new NoSuchElementException();
}
return (E)array[1];
}
public boolean isEmpty() {
return size == 0;
}
public Object[] toArray() {
return Arrays.copyOf(array, size + 1);
}
}
위 코드는 아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.
[소스코드 모아보기]
kdgyun/Data_Structure
Contribute to kdgyun/Data_Structure development by creating an account on GitHub.
github.com
- 정리
오늘은 다른 때와 달리 매우 간단하게 구현해보았다. 다른 포스팅 때 처럼 toArray, clone 등 여러 메소드를 굳이 구현하지 않는 이유는 어차피 우선순위 큐에서 모두 다뤄질 것이기 때문이다.
이미 위 자체로도 우선순위 큐로 활용이 가능하지만, 일단 여기서는 힙 구조가 어떤 구조인지를 파악하고 그 다음 우선순위 큐 파트에서 좀 더 다양한 메소드들을 구현하고자 하니 오늘은 개념만 익히는 것에 중점을 두었다.
아 위에서 구현한 코드가 잘 작동하는지 궁금하실 수도 있겠다.
마지막으로 테스트 한 것을 보여주고 이 포스팅을 마치도록 하겠다.
일단 먼저 primitive type일 경우다. 랜덤 값으로 값을 넣어주었다.
[test.java]
import java.util.Random;
public class test {
public static void main(String[] args) {
Heap<Integer> heap = new Heap<>();
Random rnd = new Random();
for(int i = 0; i < 15; i++) {
heap.add(rnd.nextInt(100));
}
// 힙 내부 배열의 요소 상태
System.out.print("내부 배열 상태 : ");
for(Object val : heap.toArray()) {
System.out.print(val + " ");
}
System.out.println();
// 힙이 비어있을 때 까지 한 개씩 요소 뽑음
System.out.print("힙 요소 뽑기 : \t");
while(!heap.isEmpty()) {
System.out.print(heap.remove() + " ");
}
}
}
[결과]
배열을 얻을 때 index 1부터 시작하기 때문에 내부 배열상태에서 맨 첫번 째가 null이 나오는 것은 정상이다.
힙 요소를 뽑을 때도 오름차순으로 잘 나온다.
사용자 정의 클래스일 경우도 테스트 해보았다.
import java.util.Comparator;
public class Test {
public static void main(String[] args) {
Heap<Student> heap1 = new Heap<Student>();
Heap<Student> heap2 = new Heap<Student>(comparator);
heap1.add(new Student("김자바", 40));
heap2.add(new Student("김자바", 40));
heap1.add(new Student("이씨프", 27));
heap2.add(new Student("이씨프", 27));
heap1.add(new Student("조파이", 48));
heap2.add(new Student("조파이", 48));
heap1.add(new Student("김자바", 18));
heap2.add(new Student("김자바", 18));
heap1.add(new Student("상스윕", 32));
heap2.add(new Student("상스윕", 32));
heap1.add(new Student("양씨샵", 27));
heap2.add(new Student("양씨샵", 27));
System.out.println("[Heap 1] : 이름순(같을 경우 나이 오름차순)");
while(!heap1.isEmpty()) {
System.out.println(heap1.remove());
}
System.out.println();
System.out.println("[Heap 2] : 나이 내림차순(같을 경우 이름순)");
while(!heap2.isEmpty()) {
System.out.println(heap2.remove());
}
System.out.println();
}
private static Comparator<Student> comparator = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// 나이가 같다면 이름순
if(o1.age == o2.age) {
return o1.name.compareTo(o2.name);
}
return o2.age - o1.age; // 나이 내림차순
}
};
private static class Student implements Comparable<Student> {
String name;
int age;
public Student(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Student o) {
// 이름이 같다면 나이순 (오름차순)
if(this.name.compareTo(o.name) == 0) {
return this.age - o.age;
}
// 이름순
return this.name.compareTo(o.name);
}
public String toString() {
return "이름 : " + name + "\t나이 : " + age;
}
}
}
heap1 은 기본 정렬을 지정하여 쓴 방식(Comparable)이고, heap2는 Comparator를 사용하여 Comparabler과는 다른 정렬방식을 지정하여 생성할 때 인자로 넘겨주었다.
결과적으로 대성공이다.
이렇게 힙을 구현해보았는데, 혹여 어렵거나 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.
'자료구조 > Java' 카테고리의 다른 글
| 자바 [JAVA] - Set Interface (셋 인터페이스) (0) | 2021.04.09 |
|---|---|
| 자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기 (24) | 2021.03.04 |
| 자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기 (6) | 2020.12.17 |
| 자바 [JAVA] - 배열을 이용한 Deque (덱) 구현하기 (6) | 2020.12.12 |
| 자바 [JAVA] - 연결리스트를 이용한 Queue (큐) 구현하기 (21) | 2020.12.09 |