Backend/자료구조
힙(heap)
chjysm
2022. 12. 20. 16:23
힙 이란?
완전 이진트리의 일종이며, 우선순위 큐를 위해 만들어진 자료구조이다.
우선순위 큐?
- 우선순위 개념을 큐에 적용한 자료 구조이다.
- 가장 우선순위가 높은 데이터가 먼저 나간다.
- 배열, 연결 리스트, 힙으로 구현 가능하다. 이중 힙으로 구현하는 것이 가장 성능이 좋다.
힙 특징
- 힙은 일종의 반정렬 상태를 유지한다.( 큰 값이 위에 있으면 작은 값은 아래에 있다는 정도 )
- 부모 노드의 값이 자식 노드보다 항상 크거나 작은 이진트리이다.
- 중복을 허용한다.
- 최대값, 최소값을 조회하기 좋다
힙 종류
- 최대 힙
- 부모 노드가 자식 노드보다 크거나 같은 완전 이진트리
- 최소 힙
- 부모 노드가 자식 노드보다 작거나 같은 완전 이진트리
힙 구현
- 힙을 저장하는 표준 자료구조는 배열이다.
- 배열의 첫 번째 인덱스인 0은 사용하지 않는다.
- 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
- 왼쪽 자식의 인덱스 = (부모의 인덱스) * 2
오른쪽 자식의 인덱스 = (부모의 인덱스) * 2 + 1
부모의 인덱스 = (자식의 인덱스) / 2
힙의 삽입
- 힙에 새로운 요소가 들어오면, 힙의 마지막 노드에 이어서 삽입한다.
- 새로운 노드를 부모 노드들과 비교하여 교환( 힙의 정의에 따라 )
힙의 삭제
- 루트 노드를 삭제한다. (최대 힙이면 루트 노드가 최대 값)
- 삭제한 노드에는 힙의 마지막 노드 가져온다.
- 재정렬( 자식 노드와 값을 비교 및 교환 )
구현
public class Heap {
// TODO comparator 를 생성자로 받아서 int 배열이 아닌 다양한 객체 배열로 사용 가능하도록 수정하자.
private static final int DEFAULT_CAPACITY = 10; // 기본 배열 사이즈
private boolean isMaxHeap; // 최대 힙 여부 ( TRUE = 최대 힙, FALSE = 최소 힙 )
private int size; // 실제 요소 개수
private int[] array; // 요소를 담을 배열
public Heap() {
this.array = new int[DEFAULT_CAPACITY];
this.size = 0;
this.isMaxHeap = false;
}
public Heap( int capacity ) {
this(capacity, false);
}
public Heap( int capacity, Boolean isMaxHeap ) {
this.array = new int[capacity];
this.size = 0;
this.isMaxHeap = isMaxHeap;
}
private int getParentIndex( int index ){
return index / 2;
}
private int getLeftChildIndex( int index ){
return index * 2;
}
private int getRightChildIndex( int index ){
return index * 2 + 1;
}
/**
* 배열 사이즈 증축
* @param newCapacity 세로운 용적 크기
* */
private void resize( int newCapacity ){
// 새 배열 생성
int[] newArray = new int[newCapacity];
// 데이터 복사
for ( int i = 1; i<= size; i++ ){
newArray[i] = array[i];
}
this.array = newArray;
}
/**
* 삽입
*/
public void add( int val ){
// 배열이 꽉찬 경우 배열 사이즈 증축
int index = size + 1;
if( index == array.length ) {
resize(array.length * 2);
}
// 2. 새로운 노드를 부모 노드들과 비교하여 교환( 힙의 정의에 따라 )
while( true ){
int parentIndex = getParentIndex(index);
int parentValue = array[parentIndex];
// 최대 힙 이냐 에 따른 조건에 따라 반복문 종료
if( isMaxHeap ){
// 최대 힙
if( parentValue >= val ){
break;
}
} else {
// 최소 힙
if( parentValue <= val ){
break;
}
}
// 종료 안되었다면 부모와 교환 해야 한다.
array[index] = parentValue;
index = parentIndex;
}
// 마지막 삽입
array[index] = val;
size++;
}
/**
* 추출
*/
public int delete(){
// 데이터 유무 확인
if( size == 0 ){
throw new NoSuchElementException();
}
// 루트 노드를 삭제한다. (최대 힙이면 루트 노드가 최대 값)
// 삭제한 노드에는 힙의 마지막 노드 가져 온다.
int result = array[1]; // 반환할 데이터
int lastOne = array[size]; // 마지막 요소
array[size] = 0; // 마지막 요소를 비운다.
size--;
// 재정렬( 자식 노드와 값을 비교 및 교환 )
int parentIndex = 1;
int childIndex;
while( ( childIndex = getLeftChildIndex( parentIndex ) ) <= size ) {
int rightIndex = getRightChildIndex( parentIndex );
int childValue = array[childIndex]; // 왼쪽 자식 값
if( isMaxHeap ){
if( rightIndex <= size && array[rightIndex] > childValue ){
// 더 큰 자식과 비교 해야한다.
childIndex = rightIndex;
childValue = array[childIndex];
}
if( lastOne >= childValue ){
break;
}
} else {
if( rightIndex <= size && array[rightIndex] < childValue ){
// 더 작은 자식과 비교 해야한다.
childIndex = rightIndex;
childValue = array[childIndex];
}
if( lastOne <= childValue ){
break;
}
}
array[parentIndex] = childValue;
parentIndex = childIndex;
}
array[parentIndex] = lastOne;
/*
* 용적의 사이즈가 최소 용적보다는 크면서 요소의 개수가 전체 용적의 1/4일경우
* 용적을 반으로 줄임(단, 최소용적보단 커야함)
*/
if( array.length > DEFAULT_CAPACITY && size < array.length / 4 ) {
resize( Math.max( DEFAULT_CAPACITY, array.length / 2 ) );
}
return result;
}
public int size() {
return this.size;
}
public int peek() {
if( array[1] == 0 ) {
throw new NoSuchElementException();
}
return array[1];
}
public boolean isEmpty() {
return size == 0;
}
public int[] toArray() {
return Arrays.copyOf(array, size + 1);
}
}
참조
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
[자료구조] 힙(heap)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
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