Java로 구현한 Heap 자료구조(트리 구조)
이번 글에서는 Heap 자료구조에 대해 설명하겠습니다.
백준 알고리즘을 푸는 글이 많은데 알고리즘과 자료구조는 굉장히 깊은 관계가 있기 때문에 자료구조에 대한 공부 한 것을 종종 기록해 공유하도록 하겠습니다.
목차
1. Heap 자료구조란?
Heap 자료구조는 Heap 정렬에서 사용되는 자료구조입니다.
이번 글에서는 단순이 int형만 만들어지는 것이 아니라 객체도 만들 수 있도록 구현하도록 하겠습니다.
상당히 복잡한 부분도 있지만 최대한 쉽게 설명할 수 있도록 해보겠습니다.
먼저 Heap이 무엇인지 알아야 합니다. Heap은 최솟값 혹은 최댓값을 빠르게 찾기 위한 완전이진트리 형식으로 만들어진 자료구조입니다.
그럼 완전이진트리가 무엇인지 알아보도록 하겠습니다.
먼저 트리 형식이란 아래와 같은 형식을 의미합니다.
트리구조란 위와 같이 나무 모양을 거꾸로 한 모양으로 이루어진 구조를 말합니다.
위에서부터 아래로 내려가는 구조로 노드들과 간선의 집합을 트리구조라고 합니다.
트리 구조를 이루는 형식에서 몇 가지 용어들이 있습니다. 편의를 위해 용어 정리를 먼저 하겠습니다.
노드 : 트리를 이루는 하나의 구성들이다. (예, A노드, B노드)
간선 : 노드를 연결하는 선
부모 노드 : 자기 자신의 노드의 연결된 하나의 LEVEL이 높은 노드(예, H의 부모노드는 D노드)
자식 노드 : 자기 자신의 노드의 연결된 하나의 LEVEL이 낮은 노드, 하위 노드라고도 한다.(예, G의 자식노든 I, J노드)
루트 노드 : LEVEL 1에 존재하는 노드로 트리 구조에 하나밖에 존재하지 않는다. 뿌리 노트라고도 한다.(예, A노드)
단말 노드 : 자식 노드가 없는 노드를 의미하고 리프 노드라고도 한다.(예, H, E, F, I, J노드)
내부 노드 : 단말 노드가 아닌 노드(예, A, B, C, D, G노드)
형제 노드 : 부모가 같은 노드(예, D, E, F 노드는 부모가 B 노드 임으로 모두 형제 노드이다.)
깊이 : 특정 노드에 도달하기 위해 거쳐야 하는 간선의 개수(예, E노드의 깊이 A->B->E임으로 2)
레벨 : 특정 깊이에 있는 노드들의 집합
차수 : 특정 노드에 연결된 자식노드의 개수(예, B의 차수 D, E, F임으로 3)
이진트리 구조란, 각 노드의 자식노드를 2개까지만 가질 수 있도록 한 것을 의미합니다.
위에 트리구조에서 E노드만 제거하면 이진트리라고 부를 수 있는 조건을 충족하게 됩니다.
여기서 완전이진트리 구조란 모든 노드들이 왼쪽부터 차례대로 채워져 있는 구조이면서 마지막 노드를 제외한 모든 노드가 채워져 있는 구조를 의미합니다.
여기에서 조건을 하나 더 추가하면 마지막 레벨을 제외한 모든 노드에는 2개의 자식노드 가진다. 를 만족하면 포화이진트리가 된다. 힙 정렬에서는 포화이진트리까지는 사용하지 않음으로 거기까지는 알아보지 않겠습니다.
그러면 이제는 이진트리에서 어떻게 빠르게 최솟값과 최댓값을 찾을지 생각해보아야 합니다.
힙 자료구조는 하나의 규칙이 있습니다. 부모노드는 자식노드보다 우선순위가 높다는 것입니다.
그렇게 된다면 루트 노드는 우선순위가 가장 높은 노드라는 뜻이고 최댓값 혹은 최솟값을 빠르게 찾아낼 수 있다는 장점(시간복잡도 : O(1))과 함께 삽입 삭제 연산 시에도 부모노드가 자식노드보다 우선순위만 높으면 되므로 결국 트리의 깊이만큼만 비교를 하면 되기 때문에 O(logN)의 시간복잡도를 갖아 매우 빠르게 수행할 수 있습니다.
힙은 두 가지로 나눠지는데 최소힙과 최대힙입니다.
최대힙은 큰 값부터 정렬되어 최댓값을 찾을 때 사용하고
최소힙은 작은 값부터 정렬되어 최솟값을 찾을 때 사용합니다.
예를 들어 아래 그림과 같습니다.
보기 편하도록 숫자로 정렬해 보았습니다. 최소힙으로 이루어져 있습니다.
그림을 보시면 조금 어색한 부분을 찾을 수 있습니다.
형제 노드 간의 우선순위를 고려하지 않았다는 것입니다.
이진트리구조에서는 오직 부모노드는 자식노드보다 우선순위가 높다라는 규칙만 적용되기 때문에 형제간의 우선순위는 고려하지 않습니다. 이러한 정렬 상태를 흔히 '반 정렬 상태' 혹은 '느슨한 정렬 상태' , '약한 힙(weak heap)'이라고도 부릅니다.
최솟값 혹은 최댓값을 찾는 것이 목적이기 때문에 형제간의 우선순위를 고려하지 않아도 됩니다.
트리구조를 구현할 방법은 배열로 구현하게 될 것입니다.
배열은 계산의 편의상 첫 번째 값(인덱스 0)은 사용하지 않을 것입니다.
그리고 ROOT노드부터 1번 인덱스에 그 왼쪽의 자식노드부터 차례대로 배열에 넣는 형식으로 구현할 것입니다.
아래 그림과 같은 형식으로 배열이 만들어질 것입니다.
트리 구조를 배열로 만들어보면 3가지 규칙이 생기는데
1. 부모노드 * 2 = 왼쪽 자식 노드
2. 부모노드 * 2 + 1 = 오른쪽 자식노드
3. 자식노드 / 2 = 부모노드
이 규칙을 구현할 때 사용해 보도록 하겠습니다.
앞에 서론이 길었는데 이제 실제로 java를 사용해 이진트리구조를 구현해 보도록 하겠습니다.
2. Heap 자료구조 Java 구현
전체 코드
import java.util.Comparator;
import java.util.NoSuchElementException;
public class Heap <E>{
private final int DEFAULT_CAPACITY = 10;//배열의 최소 용적 길이
private int size;//실제 배열에 입력된 노드의 개수
private Object[] array;//heap 자료구조를 넣을 배열
private Comparator<? super E> comparator;//사용자가 지정할 comparator
/*
* Heap의 생성자는 총 4개로 이루어져 있다.
* 1. 기본 생성자 : 배열의 길이을 10으로 설정하며 comparator 객체가 없는 생성자
* 2. 배열 길이 생성자 : 배열이 길이를 지정해주며 comparator 객체가 없는 생서자
* 3. comparator 생성자 : 배열의 길이를 10으로 설정하며 comparator 객체가 있는 생성자
* 4. 배열 길이 comparator 생성자 : 배열의 길이와 comparator 객체가 있는 생성자
*/
public Heap(){this(null);}
public Heap(int capacity){this(capacity,null);}
public Heap(Comparator<? super E> comparator){
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
public Heap(int capacity,Comparator<? super E> comparator){
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}
/*
* @idx 배열의 인덱스
* 부모 노드 인덱스 번호를 구하는 함수
*/
private int getParent(int idx){return idx/2;}
/*
* @idx 배열의 인덱스
* 왼쪽 자식 노드 인덱스 번호를 구하는 함수
*/
private int getChildLeft(int idx){return idx*2;}
/*
* @idx 배열의 인덱스
* 오른쪽 자식 노드 인덱스 번호를 구하는 함수
*/
private int getChildRight(int idx){return idx*2+1;}
/*
* @newCapacity 새로운 배열의 용적 길이
* 배열의 길이가 줄거나 늘었을 경우에 새로 용적을 지정하는 함수
*/
private void resize(int newCapacity){
Object[] newArray = new Object[newCapacity];
//속도를 위해 배열의 모든 값을 하지 않고 유의미한 값만 newArray에 입력합니다.
for(int i=0; i<=size; i++){
newArray[i] = array[i];
}
//array를 newArray에 링크합니다.
array = newArray;
}
/*
* @target 추가된 객체
* 객체 추가하는 함수
*/
public void add(Object target){
//배열이 가득차면 배열을 2배로 늘린다.
if(size+1 == array.length){
resize(array.length*2);
}
//새로운 노드를 입력
siftUp(target,size+1);
//노드가 정상적으로 입력되면
size++;
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftUp(Object target, int idx){
if(comparator != null){
siftUpComparator(target,idx,comparator);
}else{
siftUpComparable(target,idx);
}
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* @comparator 사용자 지정 비교 객체
*/
private void siftUpComparator(Object target, int idx, Comparator<? super E> comparator){
//루트 인덱스까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드의 인덱스
//부모노드의 우선순위가 높으면 반복문 종료
if(comparator.compare((E)target,(E)array[parent]) > 0){
break;
}
//반복문이 종료되지 안핬다면 자식 노드에 부모 노드를 입력하고 비교 인덱스를 부모 인덱스로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되면 해당 인덱스에 추가 객체를 입력
array[idx] = target;
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 사용자가 지정하지 않은 정렬의 추가 함수
*/
private void siftUpComparable(Object target, int idx){
//compareTo를 사용하기 위해 target을 형변환
Comparable<? super E> comp = (Comparable<? super E>) target;
//루투 노드까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드 인덱스
//부모 노드가 자식노드보다 우선순위가 높으면 반복문 종료
if(comp.compareTo((E)array[parent]) > 0){
break;
}
//반복문이 종료되지 않았다면 부모 노드를 자식 노드에 입력, 인덱스를 부모 노드로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되었다면 target를 해당 인덱스에 입력
array[idx] = comp;
}
/*
* 루트 노드를 리턴하고 삭제하는 함수
*/
public E remove(){
//루트 노드가 업다면 오류 출력
if(array[1] == null){
throw new NoSuchElementException();
}
E target = (E)array[size];//루트 노드 삭제 후 재정렬 하기 위해 target 노드 설정
E result = (E)array[1];//루트 노드를 리턴하기 위한 변수 초기화
array[size] = null;//마지막 배열 null 입력
size--; //size를 미리 줄여주지 않아면 비교 과정에서 outofindex 에러가 날 수 있어 미리 줄여준다.
siftDown(target,1);//삭제 후 재배열하는 함수
return result;
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftDown(E target, int idx){
if(comparator != null){
siftDownComparator(target, idx, comparator);
}else{
siftDownComparable(target,idx);
}
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* @comp 사용자 지정 우선순위
* 사용자가 지정한 우선순위가 존재하는 삭제시 재배열 함수
*/
private void siftDownComparator(E target, int idx, Comparator<? super E> comp){
array[idx] = null;//루트 인덱스 null처리
int child;
int childLeft;//자식 왼쪽 인덱스
int childRight;//자식 오른쪽 인덱스
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childLeft = getChildLeft(idx);
childRight = getChildRight(idx);
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && comp.compare((E)array[childLeft],(E)array[childRight]) > 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compare((E)array[child],(E)target) > 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* 사용자가 지정한 우선순위가 존재하지 않는 삭제시 재배열 함수
*/
private void siftDownComparable(E target, int idx){
array[idx] = null;//루트 인덱스 null처리
Comparable<? super E> comp = (Comparable<? super E>) target;
int child;
int childRight;//자식 오른쪽 인덱스
int childLeft;
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childRight = getChildRight(idx);
childLeft = getChildLeft(idx);
Comparable<? super E> childRightVal = (Comparable<? super E>) array[childRight];
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && childRightVal.compareTo((E)array[childLeft]) < 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compareTo((E)array[child]) < 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}
}
기본적으로 제네릭과 comparable, comparator에 대한 이해가 있다고 생각하고 작성하겠습니다.
나중에 제네릭과 comparable, comparator에 대한 이야기도 해보도록 하겠습니다.
1) Heap 자료구조의 생성자와 변수
먼저 생성자와 변수에 대해 이야기해 보도록 하겠습니다.
public class Heap <E>{
private final int DEFAULT_CAPACITY = 10;//배열의 최소 용적 길이
private int size;//실제 배열에 입력된 노드의 개수
private Object[] array;//heap 자료구조를 넣을 배열
private Comparator<? super E> comparator;//사용자가 지정할 comparator
/*
* Heap의 생성자는 총 4개로 이루어져 있다.
* 1. 기본 생성자 : 배열의 길이을 10으로 설정하며 comparator 객체가 없는 생성자
* 2. 배열 길이 생성자 : 배열이 길이를 지정해주며 comparator 객체가 없는 생서자
* 3. comparator 생성자 : 배열의 길이를 10으로 설정하며 comparator 객체가 있는 생성자
* 4. 배열 길이 comparator 생성자 : 배열의 길이와 comparator 객체가 있는 생성자
*/
public Heap(){this(null);}
public Heap(int capacity){this(capacity,null);}
public Heap(Comparator<? super E> comparator){
this.array = new Object[DEFAULT_CAPACITY];
this.size = 0;
this.comparator = comparator;
}
public Heap(int capacity,Comparator<? super E> comparator){
this.array = new Object[capacity];
this.size = 0;
this.comparator = comparator;
}먼저 heap 자료구조에 어떤 형식의 객체도 들어올 수 있도록 제네릭으로 만들도록 하겠습니다.
기본적으로 실제 배열에 입력된 노드의 개수와 실제 배열의 길이는 다릅니다.
입력하거나 삭제할 때 용의 하도록 배열의 길이를 넉넉하게 잡아줍니다.
DEFAULT_CAPACITY : 실제 배열의 길이의 최솟값입니다. 10 이하로는 배열의 길이를 줄이지 않습니다.
size : 실제 입력된 노드의 개수입니다. 이 array.length로 실제 노드의 개수를 알 수 없으니 이 변수를 사용합니다.
array : heap 자료구조로 이용될 배열입니다. 노드 값이 이곳에 저장됩니다.
comparator : 사용자가 설정한 정렬 기준입니다.
생성자는 총 4개지로 나누어지는데 test과정에서 4가지 모두 사용해서 test 해보도록 하겠습니다.
해당 생성자는 배열의 사이즈를 객체를 생성할 때 지정, 정렬 기준을 지정하는지에 따라 4가지로 구분되어 있습니다.
2) Heap 자료구조의 인덱스 구하는 함수와 배열 길의 재정의 함수
그다음은 위에 말씀드렸던 힙자료구조의 규칙을 이용한 함수를 말씀드리도록 하겠습니다.
/*
* @idx 배열의 인덱스
* 부모 노드 인덱스 번호를 구하는 함수
*/
private int getParent(int idx){return idx/2;}
/*
* @idx 배열의 인덱스
* 왼쪽 자식 노드 인덱스 번호를 구하는 함수
*/
private int getChildLeft(int idx){return idx*2;}
/*
* @idx 배열의 인덱스
* 오른쪽 자식 노드 인덱스 번호를 구하는 함수
*/
private int getChildRight(int idx){return idx*2+1;}주석에 있는 그대로 부모와 자식을 구하는 함수입니다.
/*
* @newCapacity 새로운 배열의 용적 길이
* 배열의 길이가 줄거나 늘었을 경우에 새로 용적을 지정하는 함수
*/
private void resize(int newCapacity){
Object[] newArray = new Object[newCapacity];
//속도를 위해 배열의 모든 값을 하지 않고 유의미한 값만 newArray에 입력합니다.
for(int i=0; i<=size; i++){
newArray[i] = array[i];
}
//array를 newArray에 링크합니다.
array = newArray;
}배열이 증가하거나 줄었을 경우 배열의 길이를 조절하는 함수입니다.
이때 실제 있는 값만 옮기기 위해 size값을 사용하여 반복문을 종료합니다.
이제는 노드를 추가하는 부분을 구현하겠습니다.
3) Heap 자료구조의 노드 추가 함수
추가하는 부분은 삭제하는 부분보다는 쉽지만 그렇다고 마냥 쉽지만은 않습니다.
그림으로 먼저 설명하도록 하겠습니다.
글로 설명하면
1. 배열의 마지막에 추가한 값을 넣습니다.
2. 배열의 부모 노드와 비교해 우선순위가 높을 시 부모노드와 값을 교환합니다.
3. 우선순위가 부모노드보다 낮거나 루트 노드가 되었을 경우가 될 때까지 2번을 반복합니다.
이제 코드로 구현해 보도록 하겠습니다.
전체 추가 코드
/*
* @target 추가된 객체
* 객체 추가하는 함수
*/
public void add(Object target){
//배열이 가득차면 배열을 2배로 늘린다.
if(size+1 == array.length){
resize(array.length*2);
}
//새로운 노드를 입력
siftUp(target,size+1);
//노드가 정상적으로 입력되면
size++;
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftUp(Object target, int idx){
if(comparator != null){
siftUpComparator(target,idx,comparator);
}else{
siftUpComparable(target,idx);
}
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* @comparator 사용자 지정 비교 객체
*/
private void siftUpComparator(Object target, int idx, Comparator<? super E> comparator){
//루트 인덱스까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드의 인덱스
//부모노드의 우선순위가 높으면 반복문 종료
if(comparator.compare((E)target,(E)array[parent]) > 0){
break;
}
//반복문이 종료되지 안핬다면 자식 노드에 부모 노드를 입력하고 비교 인덱스를 부모 인덱스로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되면 해당 인덱스에 추가 객체를 입력
array[idx] = target;
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 사용자가 지정하지 않은 정렬의 추가 함수
*/
private void siftUpComparable(Object target, int idx){
//compareTo를 사용하기 위해 target을 형변환
Comparable<? super E> comp = (Comparable<? super E>) target;
//루투 노드까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드 인덱스
//부모 노드가 자식노드보다 우선순위가 높으면 반복문 종료
if(comp.compareTo((E)array[parent]) > 0){
break;
}
//반복문이 종료되지 않았다면 부모 노드를 자식 노드에 입력, 인덱스를 부모 노드로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되었다면 target를 해당 인덱스에 입력
array[idx] = comp;
}총 4가지 함수로 이루어져 있습니다. 함수를 하나씩 설명해 드리도록 하겠습니다.
/*
* @target 추가된 객체
* 객체 추가하는 함수
*/
public void add(Object target){
//배열이 가득차면 배열을 2배로 늘린다.
if(size+1 == array.length){
resize(array.length*2);
}
//새로운 노드를 입력
siftUp(target,size+1);
//노드가 정상적으로 입력되면
size++;
}해당 함수는 실제로 메인에서 타깃을 넣을 때 실행되는 함수입니다. 배열을 넣기 위해 배열 길이를 늘이고 배열이 입력되면 size를 늘리는 노드를 입력하기 위한 준비를 하는 함수입니다.
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftUp(Object target, int idx){
if(comparator != null){
siftUpComparator(target,idx,comparator);
}else{
siftUpComparable(target,idx);
}
}실제로 노드를 입력하는 부분을 실행하기 전에 comparator이 있는지 없는지 검사하는 함수입니다. 사용자가 지정한 정렬 기준이 있다면 comparator을 사용하는 함수로 없다면 해당 객체에 comaprable이 구현되어 있을 것임으로 comarable을 사용하는 함수를 실행합니다.
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* @comparator 사용자 지정 비교 객체
*/
private void siftUpComparator(Object target, int idx, Comparator<? super E> comparator){
//루트 인덱스까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드의 인덱스
//부모노드의 우선순위가 높으면 반복문 종료
if(comparator.compare((E)target,(E)array[parent]) > 0){
break;
}
//반복문이 종료되지 안핬다면 자식 노드에 부모 노드를 입력하고 비교 인덱스를 부모 인덱스로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되면 해당 인덱스에 추가 객체를 입력
array[idx] = target;
}
/*
* @target 추가된 객체
* @idx 추가된 객체의 인덱스
* comparator 사용자가 지정하지 않은 정렬의 추가 함수
*/
private void siftUpComparable(Object target, int idx){
//compareTo를 사용하기 위해 target을 형변환
Comparable<? super E> comp = (Comparable<? super E>) target;
//루투 노드까지 반복
while(1 < idx){
int parent = getParent(idx);//부모 노드 인덱스
//부모 노드가 자식노드보다 우선순위가 높으면 반복문 종료
if(comp.compareTo((E)array[parent]) > 0){
break;
}
//반복문이 종료되지 않았다면 부모 노드를 자식 노드에 입력, 인덱스를 부모 노드로 입력
array[idx] = array[parent];
idx = parent;
}
//반복문이 종료되었다면 target를 해당 인덱스에 입력
array[idx] = comp;
}실제로 입력하는 부분입니다.
"기본 구성은 루트 노드까지 반복하고 우선순위가 부모 노드가 높으면 반복문을 종료한다."로 이루어져 있습니다.
만약 부모노드가 우선순위가 낮다면 부모노드를 자식노드로 내리고 해당 인덱스를 부모노드로 입력하도록 구현합니다.
여기서 주의할 점은 if(comparator.compare((E) target, (E) array [parent]) > 0) 이 문을 사용할 때
if(comparator.compare((E) array [idx], (E) array [parent]) > 0)처럼 구현하면 안 된다는 것입니다. 이유는 해당 인덱스에 아직 값이 입력이 되지 않았기 때문에 에러가 날 수 있거나 잘못된 값이 비교될 수 있기 때문입니다.
그다음은 제거하는 함수입니다.
힙 자료구조에서 가장 복잡한 부분입니다.
4) Heap 자료구조의 삭제 함수
힙 자료구조에서 제거란 루트 값을 출력하고 제거하는 작업입니다.
즉, 최솟값이나 최댓값을 뽑아내는 과정이죠. 뽑아낸 후에는 그 값이 제거되고 배열 안에서 재배치가 일어나 다음에 최솟값이나 최댓값을 루트 노드를 통해 찾아낼 수 있도록 합니다.
해다 과정은 정렬을 할 때 큰 도움이 됩니다.
그러면 먼저 어떤 식으로 제거가 되는지 알아보도록 하겠습니다.
글로 설명하면
1. 루트노드를 먼저 출력합니다.
2. 마지막 인덱스에 있는 노드 값을 루트로 올립니다. 해당 노드가 타깃 노드가 됩니다.
3. 타깃 노드의 자식 노드 중 더 우선순위가 높은 노드와 비교합니다.
4. 우선순위가 자식노드가 더 높다면 해당 타깃노드와 자식노드의 위치를 변경합니다.
5. 타깃노드의 우선순위가 더 높아질 때까지 4번을 반복하다가 타깃노드의 우선순위가 높아졌다면 해당 노드에 타깃노드 값을 입력합니다.
다음과 같습니다.
이제 코드로 구현해 보도록 하겠습니다.
삭제 전체 코드
/*
* 루트 노드를 리턴하고 삭제하는 함수
*/
public E remove(){
//루트 노드가 업다면 오류 출력
if(array[1] == null){
throw new NoSuchElementException();
}
E target = (E)array[size];//루트 노드 삭제 후 재정렬 하기 위해 target 노드 설정
E result = (E)array[1];//루트 노드를 리턴하기 위한 변수 초기화
array[size] = null;//마지막 배열 null 입력
size--; //size를 미리 줄여주지 않아면 비교 과정에서 outofindex 에러가 날 수 있어 미리 줄여준다.
siftDown(target,1);//삭제 후 재배열하는 함수
return result;
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftDown(E target, int idx){
if(comparator != null){
siftDownComparator(target, idx, comparator);
}else{
siftDownComparable(target,idx);
}
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* @comp 사용자 지정 우선순위
* 사용자가 지정한 우선순위가 존재하는 삭제시 재배열 함수
*/
private void siftDownComparator(E target, int idx, Comparator<? super E> comp){
array[idx] = null;//루트 인덱스 null처리
int child;
int childLeft;//자식 왼쪽 인덱스
int childRight;//자식 오른쪽 인덱스
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childLeft = getChildLeft(idx);
childRight = getChildRight(idx);
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && comp.compare((E)array[childLeft],(E)array[childRight]) > 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compare((E)array[child],(E)target) > 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* 사용자가 지정한 우선순위가 존재하지 않는 삭제시 재배열 함수
*/
private void siftDownComparable(E target, int idx){
array[idx] = null;//루트 인덱스 null처리
Comparable<? super E> comp = (Comparable<? super E>) target;
int child;
int childRight;//자식 오른쪽 인덱스
int childLeft;
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childRight = getChildRight(idx);
childLeft = getChildLeft(idx);
Comparable<? super E> childRightVal = (Comparable<? super E>) array[childRight];
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && childRightVal.compareTo((E)array[childLeft]) < 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compareTo((E)array[child]) < 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}
이것 역시 총 4가지 함수로 이루어져 있습니다.
하나씩 살펴보도록 하겠습니다.
/*
* 루트 노드를 리턴하고 삭제하는 함수
*/
public E remove(){
//루트 노드가 업다면 오류 출력
if(array[1] == null){
throw new NoSuchElementException();
}
E target = (E)array[size];//루트 노드 삭제 후 재정렬 하기 위해 target 노드 설정
E result = (E)array[1];//루트 노드를 리턴하기 위한 변수 초기화
array[size] = null;//마지막 배열 null 입력
size--; //size를 미리 줄여주지 않아면 비교 과정에서 outofindex 에러가 날 수 있어 미리 줄여준다.
siftDown(target,1);//삭제 후 재배열하는 함수
return result;
}실제 삭제할 때 호출하는 함수입니다. return값으로 루트 값을 return 하고 만약 노드가 없는데 삭제를 한다면 예외를 시켜줍니다. 마지막 배열은 target으로 입력 후 배열에서 삭제해 줍니다. 그리고 미리 size을 줄여줘야 하는데 줄여주지 않으면 해당 타깃 노드를 비교하는 과정에서 에러가 출력됩니다.
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* comparator 생성 여부 체크 함수
*/
private void siftDown(E target, int idx){
if(comparator != null){
siftDownComparator(target, idx, comparator);
}else{
siftDownComparable(target,idx);
}
}노드를 입력했을 때와 마찬가지로 comaprator이 있는지 없는지 검사하는 함수입니다.
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* @comp 사용자 지정 우선순위
* 사용자가 지정한 우선순위가 존재하는 삭제시 재배열 함수
*/
private void siftDownComparator(E target, int idx, Comparator<? super E> comp){
array[idx] = null;//루트 인덱스 null처리
int child;
int childLeft;//자식 왼쪽 인덱스
int childRight;//자식 오른쪽 인덱스
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childLeft = getChildLeft(idx);
childRight = getChildRight(idx);
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && comp.compare((E)array[childLeft],(E)array[childRight]) > 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compare((E)array[child],(E)target) > 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}
/*
* @target 재배열을 하기 위한 타켓 노드
* @idx 루트 인덱스
* 사용자가 지정한 우선순위가 존재하지 않는 삭제시 재배열 함수
*/
private void siftDownComparable(E target, int idx){
array[idx] = null;//루트 인덱스 null처리
Comparable<? super E> comp = (Comparable<? super E>) target;
int child;
int childRight;//자식 오른쪽 인덱스
int childLeft;
//childleft보다 size가 작다면 자식 노드가 없다는 의미임으로 반복문을 종료
while((child = getChildLeft(idx)) <= size){
childRight = getChildRight(idx);
childLeft = getChildLeft(idx);
Comparable<? super E> childRightVal = (Comparable<? super E>) array[childRight];
//오른쪽 자식 노드가 있다는 가정하에 비교를 합니다. 없을경우 왼쪽 자식으로 입력
if(childRight <= size && childRightVal.compareTo((E)array[childLeft]) < 0){
child = childRight;
}
//자식 노드가 우선순위가 더 낮을 경우 반복문 종료
if(comp.compareTo((E)array[child]) < 0){
break;
}
//반복문이 종료되지 않았을 경우 부모 노드에 자식 노드를 입력하고 인덱스를 자식 인덱스로 변경
array[idx] = array[child];
idx = child;
}
//반복문이 종료되었을 경우에 target을 해당 인덱스에 입력
array[idx] = target;
//배열의 사이즈가 줄었을 경우 용량 관리를 위해 배열의 길이를 새로 정의
if(array.length > DEFAULT_CAPACITY && size < array.length/4){
resize(Math.max(DEFAULT_CAPACITY,array.length/2));
}
}해당 코드의 핵심은 언제까지 반복을 할지 그리고 어떻게 자식노드를 비교할지를 결정해야 한다는 것입니다.
일단 반복문은 자식노드가 없을 때까지 반복을 해야 합니다. 자식노드가 없다는 건 더 이상 우선순위가 낮은 노드가 없다는 뜻이기 때문에 종료를 하면 됩니다. 즉 코드에서 childLeft노드가 size보다 크다면 반복문을 종료하면 됩니다. 여기서 child에 미리 childLeft값을 넣어놓은 이유는 child에 값이 if문 안에만 있으면 target와 비교가 되지 않기 때문에 childLeft로 넣어놨습니다. 만약에 rigth가 노드가 없다면 당연히 비교해야 하는 child노드는 left노드이기 때문에 기본값으로 left노드를 넣어놓은 것입니다.(child는 target와 비교할 노드로 자식 노드 중에서 우선순위가 높은 노드를 의미합니다.) 아래 자식노드끼리 비교하는 조건을 보시면 childRigth < size라는 구분이 있습니다. 오른쪽 노드가 없을 시 비교를 하게 되면 에러가 나기 때문에 해당 구분을 넣어둔 것입니다. 이런 상황들을 잘 생각하여서 코드를 구현해야 합니다.
나머지는 똑같습니다. 반복문이 종료되지 않았다면 해당 인덱스에 자식 인덱스의 값을 넣고 인덱스 값을 자식 인덱스를 변경해시 켜 주면 됩니다. 반복문이 종료되었다면 해당 인덱스에 타깃 인덱스 값을 넣어주면 됩니다.
마지막으로 배열의 값이 줄었을 시 배열을 길이를 줄여주는 구문도 넣어줍니다.
3. Heap 자료구조 TEST
네, 이것으로 힙 자료구조 구현이 끝났습니다. 해당 자료구조를 메인 함수에서 실행시켜 보도록 하겠습니다.
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
Heap<Integer> heap = new Heap<Integer>();
//랜덤 숫자 100개 입력
for(int i=0; i<100; i++){
heap.add((int)(Math.random() * 100));
}
//최소값 순서대로 출력
for(int i=0; i<100; i++){
System.out.printf("%d ", heap.remove());
if((i+1)%10==0){
System.out.println();
}
}
System.out.println("--------------------------------");
Student[] st = {new Student("James",40),
new Student("John",27),
new Student("Robert", 58),
new Student("Michael",17),
new Student("William",31),
new Student("David", 58),
new Student("Richard",22),
new Student("Joseph",84),
new Student("Charles", 11),
new Student("Daniel",27)};
//객체 입력
Heap<Student> heap1 = new Heap<Student>(11);
for(int i=0; i<10; i++){
heap1.add(st[i]);
}
//객체 이름순으로 최소힙으로 출력
for(int i=0; i<10; i++){
Student resultSt = heap1.remove();
System.out.println("이름 : " + resultSt.name + " 나이 : " + resultSt.age);
}
System.out.println("--------------------------------");
Comparator<Student> comparator = new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
if(o1.age - o2.age == 0){
return o1.name.compareTo(o2.name);
}
return o1.age - o2.age;
}
};
//객체 나이순으로 입력
Heap<Student> heap2 = new Heap<Student>(12,comparator);
for(int i=0; i<10; i++){
heap2.add(st[i]);
}
//나이순으로 최소값부터 출력
for(int i=0; i<10; i++){
Student resultSt = heap2.remove();
System.out.println("이름 : " + resultSt.name + " 나이 : " + resultSt.age);
}
}
}
class Student implements Comparable<Student> {
public String name;
public 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;
}
//String에 comparable 인터페이스가 구현되어 있기 때문에 가능
return this.name.compareTo(o.name);
}
}
결과
숫자와 객체, 객체를 comparator과 comparable을 이용해 정렬된 값으로 출력되도록 해보았습니다.
메인 함수에서 궁금한 것이 있다면 댓글로 달아주세요. 설명해 드리도록 하겠습니다.
감사합니다.
해당 블로거를 참고하였습니다.
https://st-lab.tistory.com/205
자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기
자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중
st-lab.tistory.com