이 글은 Heap 자료구조에 대한 개념을 이해하고 있는 상태에서
직접 구현해보며 내부 동작 원리를 학습하기 위한 목적으로 작성되었습니다.
https://hyeonni.tistory.com/42
Heap 의 기본 개념 포스터이다.
요구사항
- 배열(Array)로 구현하기
- 크기 동적으로 조절하기
- reference type 도 사용할 수 있도록 제네릭 적용
- 사용자 정의 비교 기준 지원 (Comparator 활용)
기능
생성자
- 초기 공간 할당 X
- 초기 공간 설정
메서드
- getParentIndex(int index) : 부모 노드 인덱스 반환
- getLeftChildIndex(int index) : 왼쪽 자식 인덱스 반환
- getRightChildIndex(int index) : 오른쪽 자식 인덱스 반환
- resize() : 내부 배열 크기 두 배로 확장
- peek() : 루트 노드 반환 (삭제 X)
- isEmpty() : 비어있는지 여부 반환
- add(E element) : 요소 삽입 후 heapify-up 수행
- remove() : 루트 노드 제거 후 heapify-down 수행
참고
- Max Heap, Min Heap 은 Comarator 설정에 따라 유연하게 결정된다.
- 배열 인덱스 기준으로 완전 이진 트리 구조를 표현하고 상위 노드와의 비교를 통해 정렬이 유지된다.
구현하기
1. 클래스 및 멤버 변수 구성
public class Heap<E> {
private final Comparator<? super E> comparator;
private int size;
private Object[] array;
private static final int DEFAULT_INITIAL_CAPACITY = 11;
}
설명
| 변수 | 설명 |
| comparator | 힙에 저장되는 요소들 간의 우선순위 비교 기준을 정의하는 객체이다. 사용자가 원하는 정렬 기준을 외부에서 주입할 수 있도록 한다. null 일수도 있다. |
| size | 현재 힙에 저장된 요소의 개수를 나타낸다. 실제 데이터가 들어있는 영역의 길이이다. |
| array | 힙의 요소들을 저장하는 배열이다. |
| DEFAULT_INITIAL_CAPACITY | 초기 힙 생성 시 기본으로 할당되는 배열의 용량을 의미한다. 요소가 추가되면 필요에 따라 배열의 크기는 동적으로 확장된다. |
2. 생성자
public class Heap<E> {
private final Comparator<? super E> comparator;
private int size;
private Object[] array;
private static final int DEFAULT_INITIAL_CAPACITY = 10;
// 생성자 1 조건 : 초기 공간 할당 X
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.comparator = comparator;
this.size = 0;
this.array = new Object[DEFAULT_INITIAL_CAPACITY];
}
// 생성자 2 조건 : 초기 공간 설정
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.comparator = comparator;
this.size = 0;
this.array = new Object[capacity];
}
}
생성자는 크게 2가지 조건에 따라 설정했다.
- 초기 공간을 지정할 것인지
- 우선순위 비교 기준을 설정할 것인지
3 - 1. 메서드 - index 구하기
// 부모 index
public int getParentIndex(int index) {
checkIndexSize(index);
return index / 2;
}
// 왼쪽 자식 index
public int getLeftChildIndex(int index) {
checkIndexSize(index);
return index * 2;
}
// 오른쪽 자식 index
public int getRightChildIndex(int index) {
checkIndexSize(index);
return index * 2 + 1;
}
private void checkIndexSize(int index) {
if (index < 0 || index > this.size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
}
배열 기반 트리 구조의 인덱스 규칙
편의상 0번 인덱스를 사용하지 않고 1번부터 사용한다. (1-indexed)
- 부모 인덱스 = index / 2
- 왼쪽 자식 인덱스 = index * 2
- 오른쪽 자식 인덱스 = index * 2 + 1
이런 규칙이 형성된다.
3 - 2. 메서드 - resize() 동적으로 크기 조절하기
힙은 요소가 추가될 때 내부 배열의 크기가 부족하면 자동으로 확장 되어야 한다.
// 동적으로 크기 조절
public void resize(int newCapacity) {
// 방법 1:
this.array = Arrays.copyOf(this.array, newCapacity);
// 방법 2:
Object[] newArray = new Object[newCapacity];
for (int i = 1; i <= size; i++) {
newArray[i] = array[i];
}
this.array = newArray;
}
사이즈를 조절할때 구현에 있어서 고민을 했는데 방법이 2가지 정도 있는 것 같다.
방법 1 : Arrays.copyOf() 사용
- Java에서 제공하는 메서드를 활용해 배열을 간단하게 복사하고 크기를 조절 할 수 있다.
- 코드가 간결하다는 장점이 있다.
방법 2 : 직접 for문으로 복사
- 내부 동작을 직접 구현하는 방식이다.
3 - 3. 메서드 - add()
간단하게 동작을 보자면
1. 요소를 가장 아래쪽에 삽입을 한다.
2. 부모노드와 비교하면서 부모노드 보다 우선순위가 낮을때 까지 swap 한다.
3. 완성
결론은 add 할 요소를 가장 마지막에 배치한뒤 부모노드보다 우선순위가 낮을때까지 swap 하면서 위로 올리는 형태이다.
public void add(E value) {
if (size + 1 == array.length) {
resize(array.length * 2);
}
heapifyUp(size + 1, value);
size++;
}
private void heapifyUp(int index, E target) {
if (Objects.isNull(this.comparator)) {
heapifyUpComparable(index, target);
} else {
heapifyUpComparator(index, target, this.comparator);
}
}
private void heapifyUpComparator(int index, E target, Comparator<? super E> comparator) {
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparator.compare(target, (E) parentValue) >= 0) {
break;
}
array[index] = parentValue;
index = parent;
}
array[index] = target;
}
private void heapifyUpComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparable.compareTo((E) parentValue) >= 0) {
break;
}
array[index] = parentValue;
index = parent;
}
array[index] = comparable;
}
1) 배열 용량 확인 & 확장
if (size + 1 == array.length) {
resize(array.length * 2);
}- 힙은 내부적으로 배열을 사용해서 요소를 추가하기 전에 공간이 있는지 확인을 한다.
- 만약 배열이 꽉 찼다면 resize()를 통해 배열의 크기를 두배로 늘린다.
2) 힙 규칙을 지키기 위한 heapifyUp
heapifyUp(size + 1, value);
size++;- 새로운 요소는 맨 마지막 인덱스에 들어간다.
- 이후 힙의 규칙을 유지하기 위해 heapifyUp() 메서드를 호출한다.
- 마지막에 size++로 힙의 요소 개수를 갱신한다.
3) heapifyUp() 내부 동작
일단 우선순위 규칙을 지키기 위해 부모 노드와 비교해 가며 새로운 값을 위로 올리는 작업을 합니다.
private void heapifyUp(int index, E target) {
if (Objects.isNull(this.comparator)) {
heapifyUpComparable(index, target);
} else {
heapifyUpComparator(index, target, this.comparator);
}
}- Comparator 가 설정되어 있다면 -> 사용자 정의 비교 기준으로 처리
- 없다면 -> 요소 자체의 기본 비교 기준(Comparable)으로 처리
3 - 1) heapifyUpComparator() : 사용자 정의 기준 사용
private void heapifyUpComparator(int index, E target, Comparator<? super E> comparator) {
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparator.compare(target, (E) parentValue) >= 0) break;
array[index] = parentValue;
index = parent;
}
array[index] = target;
}- 부모보다 우선순위가 높을 경우 위로 끌어올림
- 최종적으로 정해진 위치에 target 저장
3 - 2) heapifyUpComparable() : 기본 정렬 기준 사용
private void heapifyUpComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparable.compareTo((E) parentValue) >= 0) break;
array[index] = parentValue;
index = parent;
}
array[index] = comparable;
}- 내부 요소가 Comparable을 구현하고 있어야 한다.
- 비교 방식은 compareTo() 사용
3 - 4. 메서드 - remove()
Heap은 가장 우선순위가 높은 요소 즉, 루트 노드를 꺼내는 구조이다.
간단하게 구현 동작을 보자면
1. 가장 우선순위가 높은것을 제거 한다. (root node)
2. 가장 마지막에 있는 node를 root 노드 자리에 배치
3. 자식 노드끼리 우선순위 비교한다
4. root 노드와 비교한다
5. 자식노드가 우선순위가 높으면 swap 한다.
결론은 root 노드에 있는것을 삭제한뒤 가장 마지막에 위치한 node를 root 노드에 배치한뒤 아래로 내려가면서 재배치하는 방식이다.
public E remove() {
if (Objects.isNull(array[1])) {
throw new NoSuchElementException();
}
E result = (E) array[1];
E target;
if (size == 1) {
target = null;
} else {
target = (E) array[size];
}
array[size] = null;
heapifyDown(1, target);
return result;
}
private void heapifyDown(int index, E target) {
if (Objects.isNull(this.comparator)) {
heapifyDownComparable(index, target);
} else {
heapifyDownComparator(index, target, this.comparator);
}
}
private void heapifyDownComparator(int index, E target, Comparator<? super E> comparator) {
array[index] = null;
size--;
int parent = index;
int child;
while ((child = getLeftChildIndex(parent)) <= size) {
int right = getRightChildIndex(parent);
Object childValue = array[child];
if (right <= size && comparator.compare((E) array[right], (E) childValue) > 0) {
child = right;
childValue = array[child];
}
if (comparator.compare(target, (E) childValue) <= 0) {
break;
}
array[parent] = childValue;
parent = child;
}
array[parent] = target;
tryShrink();
}
private void heapifyDownComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
array[index] = null;
size--;
int parent = index;
int child;
while ((child = getLeftChildIndex(parent)) <= size) {
int right = getRightChildIndex(parent);
Object childValue = array[child];
if (right <= size && ((Comparable<? super E>) childValue).compareTo((E) array[right]) > 0) {
child = right;
childValue = array[child];
}
if (comparable.compareTo((E) childValue) <= 0) {
break;
}
array[parent] = childValue;
parent = child;
}
array[parent] = target;
tryShrink();
}
private void tryShrink() {
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
1) 비어 있는지 확인
if (Objects.isNull(array[1])) {
throw new NoSuchElementException();
}- 1-indexed 구조에서 root 는 array[1] 이다.
- 루트가 null이면 요소가 없는 것이므로 예외가 발생한다.
2) 제거 대상 추출
E result = (E) array[1]; // 반환할 루트 값
E target;
if (size == 1) {
target = null;
} else {
target = (E) array[size]; // 맨 마지막 요소를 가져와서 루트에 올릴 예정
}
array[size] = null; // 마지막 요소 제거- root 값을 result에 저장해 반환할 준비를 한다.
- 그 후 마지막 요소를 가져와 루트 자리를 채울 target으로 설정한다.
- 마지막 위치는 null로 비워준다.
3) 정렬 복구 heapifyDown()
heapifyDown(1, target);- 힙의 규칙을 유지하기 위해 루트에서부터 아래로 내려가며 자리를 찾아가는 과정이다.
- 부모 - 자식 비교를 통해 우선순위가 낮은 쪽으로 내려보낸다.
동작 방식
- 배열에서 index 위치 제거 (null 처리)
- size 감소
- target 값을 아래로 내려가며 자식과 비교
- 적절한 위치에 삽입
- 필요시 배열 축소 (메모리 절약)
3 - 1) heapifyDownComparator() : 사용자 정의 기준
if (right 자식이 있고, 우측 자식 < 좌측 자식) {
child = right;
}
if (target <= childValue) break;
→ 자식 값을 부모로 끌어올리고 target을 아래로 이동
3 - 2) heapifyDownComparable() : 기본 비교 기준
if (right 자식이 있고, right < left) {
child = right;
}
if (target <= childValue) break;
→ 자식 값을 부모로 끌어올리고 target을 아래로 이동
- 왼쪽과 오른쪽 자식 노드의 값을 비교하여 둘 중 우선순위가 더 높은 자식 노드를 선택한다.
- 선택된 자식 노드와 target 값을 비교하여 힙의 규칙을 어긴다면 자식 값을 부모 위치로 올리고
- target 을 알래로 계속 내려보내면서 적절한 위치를 찾아 재배치합니다.
4) tryShrink() : 배열 자동 축소 (메모리 최적화)
private void tryShrink() {
if (array.length > DEFAULT_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_CAPACITY, array.length / 2));
}
}
- remove() 를통해 힙에서 요소가 제거된 다음에 실행된다.
- 요소가 줄어들어도 배열은 한번 늘어난 크기를 계속 유지한다.
- 이럴 경우에는 메모리 낭비가 생길 수 있어 동적으로 관리를 하는거다.
4. 전체 코드
import java.util.Arrays;
import java.util.Comparator;
import java.util.NoSuchElementException;
import java.util.Objects;
public class Heap<E> {
private final Comparator<? super E> comparator;
private static final int DEFAULT_INITIAL_CAPACITY = 10;
private int size;
private Object[] array;
// 생성자 1 조건 : 초기 공간 할당 X
public Heap() {
this(null);
}
public Heap(Comparator<? super E> comparator) {
this.comparator = comparator;
this.size = 0;
this.array = new Object[DEFAULT_INITIAL_CAPACITY];
}
// 생성자 2 조건 : 초기 공간 설정
public Heap(int capacity) {
this(capacity, null);
}
public Heap(int capacity, Comparator<? super E> comparator) {
this.comparator = comparator;
this.size = 0;
this.array = new Object[capacity];
}
// 부모 index
public int getParentIndex(int index) {
checkIndexSize(index);
return index / 2;
}
// 왼쪽 자식 index
public int getLeftChildIndex(int index) {
checkIndexSize(index);
return index * 2;
}
// 오른쪽 자식 index
public int getRightChildIndex(int index) {
checkIndexSize(index);
return index * 2 + 1;
}
private void checkIndexSize(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("Index out of bounds");
}
}
// 동적으로 크기 조절
public void resize(int newCapacity) {
// 방법 1:
this.array = Arrays.copyOf(this.array, newCapacity);
// 방법 2:
// Object[] newArray = new Object[newCapacity];
// for (int i = 1; i <= size; i++) {
// newArray[i] = array[i];
// }
// this.array = newArray;
}
public int getSize() {
return this.size;
}
public E peek() {
if (Objects.isNull(array[1])) {
throw new NoSuchElementException("Heap is empty");
}
return (E) array[1];
}
public boolean isEmpty() {
return size == 0;
}
public void add(E value) {
if (size + 1 == array.length) {
resize(array.length * 2);
}
heapifyUp(size + 1, value);
size++;
}
private void heapifyUp(int index, E target) {
if (Objects.isNull(this.comparator)) {
heapifyUpComparable(index, target);
} else {
heapifyUpComparator(index, target, this.comparator);
}
}
private void heapifyUpComparator(int index, E target, Comparator<? super E> comparator) {
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparator.compare(target, (E) parentValue) >= 0) {
break;
}
array[index] = parentValue;
index = parent;
}
array[index] = target;
}
private void heapifyUpComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
while (index > 1) {
int parent = getParentIndex(index);
Object parentValue = array[parent];
if (comparable.compareTo((E) parentValue) >= 0) {
break;
}
array[index] = parentValue;
index = parent;
}
array[index] = comparable;
}
public E remove() {
if (Objects.isNull(array[1])) {
throw new NoSuchElementException();
}
E result = (E) array[1];
E target;
if (size == 1) {
target = null;
} else {
target = (E) array[size];
}
array[size] = null;
heapifyDown(1, target);
return result;
}
private void heapifyDown(int index, E target) {
if (Objects.isNull(this.comparator)) {
heapifyDownComparable(index, target);
} else {
heapifyDownComparator(index, target, this.comparator);
}
}
private void heapifyDownComparator(int index, E target, Comparator<? super E> comparator) {
array[index] = null;
size--;
int parent = index;
int child;
while ((child = getLeftChildIndex(parent)) <= size) {
int right = getRightChildIndex(parent);
Object childValue = array[child];
if (right <= size && comparator.compare((E) array[right], (E) childValue) > 0) {
child = right;
childValue = array[child];
}
if (comparator.compare(target, (E) childValue) <= 0) {
break;
}
array[parent] = childValue;
parent = child;
}
array[parent] = target;
tryShrink();
}
private void heapifyDownComparable(int index, E target) {
Comparable<? super E> comparable = (Comparable<? super E>) target;
array[index] = null;
size--;
int parent = index;
int child;
while ((child = getLeftChildIndex(parent)) <= size) {
int right = getRightChildIndex(parent);
Object childValue = array[child];
if (right <= size && ((Comparable<? super E>) childValue).compareTo((E) array[right]) > 0) {
child = right;
childValue = array[child];
}
if (comparable.compareTo((E) childValue) <= 0) {
break;
}
array[parent] = childValue;
parent = child;
}
array[parent] = target;
tryShrink();
}
private void tryShrink() {
if (array.length > DEFAULT_INITIAL_CAPACITY && size < array.length / 4) {
resize(Math.max(DEFAULT_INITIAL_CAPACITY, array.length / 2));
}
}
}
이번 글에서는 Heap 자료구조를 직접 구현하며,
내부 동작 원리를 하나씩 따라가 보았다.
'자료구조' 카테고리의 다른 글
| [자료구조] ArrayList는 배열이 꽉찼을때 어떻게 하는가 (3) | 2025.07.31 |
|---|---|
| [자료구조] 힙(Heap) 이란 뭘까? (1) | 2024.05.09 |
