1. Heap이란?
- 힙은 우선순위 큐의 대표적인 자료구조이다.
- 우선순위큐란 원소에 우선순위가 가장 큰 원소부터 접근이 가능한 자료구조이다.
- 힙의 대표적인 종류로는 최대힙, 최소힙이 있으며 최대힙은 키값이 큰 원소가 높은 우선순위를, 최소힙은 키값이 작은 원소가 높은 우선순위를 가진다.
- 최대힙 - 부모 노드의 원소가 자식 노드의 원소보다 크거나 같은 완전 이진트리
- 최소힙 - 부모 노드의 원소가 자식 노드의 원소보다 작거나 같은 완전 이진트리
- 힙에서 삽입 및 삭제의 시간 복잡도는 O(log2n)이다.
2. (최대)Heap 구현하기
구현할 내용은 아래와 같다.
- heapifyUp(int i) - i번째 인덱스의 값을 부모 노드와 비교하여, 부모 노드의 값이 더 작으면 자리를 교환한다.
- heapifyDwon(int i) - i번째 인덱스의 값을 자식 노드 두 개와 비교하여, 둘 중 큰 자식노드보다 i번째 인덱스 값이 더 작으면 자리를 교환한다.
- insert(E x) - 힙의 적절한 자리에 입력받은 값 x를 입력한다.
- delete() - 루트 노드에 있는 값을 삭제한다.
- max() - 루트 노드에 있는 값을 리턴한다.
- isEmpty() - 힙이 비어있으면 true, 그렇지 않으면 false를 리턴한다.
- clear() - 힙의 모든 내용물을 비운다.
- printAll() - 힙의 모든 내용물을 출력한다.
** 원래 힙에서는 맨 앞의 값에만 접근이 가능하나, 테스트 편의상 printAll() 메서드를 만들어 사용하였다.
1) 인터페이스
public interface heapInterface<E> {
public void insert (E x);
public void delete();
public E max();
public boolean isEmpty();
public void clear();
public void printAll();
}
2) 클래스
- 필드 영역
//필드 영역
private E[] item;
private int size;- item[] - 원소를 저장한다.
- size - 배열에 저장된 원소의 개수를 저장한다.
- 생성자 영역
//생성자 영역
public heap(int arraySize) {
item = (E[]) new Comparable [arraySize];
size=0;
}- 배열의 크기를 입력받아 해당 크기의 배열을 생성한다. size변수는 0으로 초기화한다.
- 메서드 영역
<heapifyUp 메서드 구현>
private void heapifyUp(int i) {
if (i<0 || i>=item.length) {
throw new IllegalArgumentException();
} else {
int parent = (i-1)/2;
if (((Comparable) item[parent]).compareTo(item[i])<0) {
E tmp = item[i];
item[i] = item[parent];
item[parent] = tmp;
heapifyUp(parent);
}
}
}- parent 변수에 입력받은 인덱스 노드의 부모 인덱스를 저장한다.
- 만약 입력받은 인덱스 노드의 값보다 부모 노드의 값이 작으면 값을 바꾼다.
- 부모 노드와 인덱스 노드의 값이 같거나, 부모 노드 값이 더 클 때까지 부모 노드에 대하여 해당 과정을 반복한다.
- 만약 입력 받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.
<heapifyDown 메서드 구현>
private void heapifyDown(int i) {
int left = 2*i+1;
int right = 2*i+2;
int max = i;
if (i<0 || i>item.length) {
throw new IllegalArgumentException();
} else {
if (left <=size-1) {
if (((Comparable) item[max]).compareTo(item[left])<0) {
max = left;
}
if (((Comparable) item[max]).compareTo(item[right])<0) {
max = right;
}
if (max!=i) {
E tmp = item[i];
item[i] = item[max];
item[max] = tmp;
heapifyDown(max); }
}
}
}- left 변수에 입력받은 인덱스 노드의 왼쪽 자식 노드 인덱스, right 변수에 오른쪽 자식 노드 인덱스를 저장한다.
- max 변수에 입력받은 인덱스를 저장한다.
- left 변수가 범위를 벗어나지 않는 동안 아래 과정을 반복한다.
- max 인덱스의 값과 left, right 인덱스 값을 비교하여 max 인덱스에 가장 큰 값의 인덱스가 들어오게 한다.
- max의 값이 입력받은 값과 다르면(자식 노드중에 더 큰 값이 있다면) 입력 받은 인덱스 노드와 max 인덱스 노드의 자리를 바꾼다.
- 입력받은 인덱스가 범위를 벗어났다면 에러를 리턴한다.
<insert 메서드 구현>
@Override
public void insert(E x) {
if (size==item.length) {
throw new IllegalArgumentException();
} else {
item[size]=x;
heapifyUp(size);
size++;
}
}- 힙의 끝에 입력받은 값을 추가한다.
- heapifyUp을 통해 해당 노드가 적절한 자리를 찾게 한다.
- size 변수를 1 증가시킨다.
- 만약 힙에 빈 자리가 없었다면 에러를 리턴한다.
<delete 메서드 구현>
@Override
public void delete() {
if (isEmpty()) {
throw new IllegalArgumentException();
} else {
item[0]=item[size-1];
size--;
heapifyDown(0);
}
}- 힙의 맨 끝자리에 있던 노드를 루트 노드 자리로 옮긴다.
- size 변수를 1 감소시킨다.
- heapifyDown을 통해 루트 노드 자리의 노드가 적절한 자리를 찾게 한다.
- 만약 힙이 비어 있었다면 에러를 리턴한다.
<max 메서드 구현>
@Override
public E max() {
if (isEmpty()) {
throw new IllegalArgumentException();
} else {
return item[0];
}
}- 힙이 비어 있다면 에러를 리턴하고, 그렇지 않다면 루트 노드의 값을 리턴한다.
<isEmpty 메서드 구현>
@Override
public boolean isEmpty() {
return (size==0);
}- size 변수가 0인지 여부를 리턴한다.
<clear 메서드 구현>
@Override
public void clear() {
item = (E[]) new Comparable [size];
size=0;
}- item 배열과 size 변수를 초기화한다.
<printAll 메서드 구현>
@Override
public void printAll() {
for (int i=0; i<size; i++) {
System.out.print(item[i]+" ");
}- 인덱스 0부터 배열 끝까지 순회하며 해당 인덱스의 값을 출력한다.
-전체 코드
public class heap<E> implements heapInterface<E> {
//필드 영역
private E[] item;
private int size;
//생성자 영역
public heap(int arraySize) {
item = (E[]) new Comparable [arraySize];
size=0;
}
//메서드 영역
private void heapifyUp(int i) {
if (i<0 || i>=item.length) {
throw new IllegalArgumentException();
} else {
int parent = (i-1)/2;
if (((Comparable) item[parent]).compareTo(item[i])<0) {
E tmp = item[i];
item[i] = item[parent];
item[parent] = tmp;
heapifyUp(parent);
}
}
}
private void heapifyDown(int i) {
int left = 2*i+1;
int right = 2*i+2;
int max = i;
if (i<0 || i>item.length) {
throw new IllegalArgumentException();
} else {
if (left <=size-1) {
if (((Comparable) item[max]).compareTo(item[left])<0) {
max = left;
}
if (((Comparable) item[max]).compareTo(item[right])<0) {
max = right;
}
if (max!=i) {
E tmp = item[i];
item[i] = item[max];
item[max] = tmp;
heapifyDown(max); }
}
}
}
@Override
public void insert(E x) {
if (size==item.length) {
throw new IllegalArgumentException();
} else {
item[size]=x;
heapifyUp(size);
size++;
}
}
@Override
public void delete() {
if (isEmpty()) {
throw new IllegalArgumentException();
} else {
item[0]=item[size-1];
size--;
heapifyDown(0);
}
}
@Override
public E max() {
if (isEmpty()) {
throw new IllegalArgumentException();
} else {
return item[0];
}
}
@Override
public boolean isEmpty() {
return (size==0);
}
@Override
public void clear() {
item = (E[]) new Comparable [size];
size=0;
}
@Override
public void printAll() {
for (int i=0; i<size; i++) {
System.out.print(item[i]+" ");
}
}
}
3) 결과 확인하기
- 코드
public class Test {
public static void main(String[] args) {
heap<Integer> lst = new heap<>(64);
lst.insert(100);
lst.insert(300);
lst.insert(400);
lst.insert(200);
lst.printAll();
System.out.println();
//100,200,300,400을 차례로 입력하고 출력합니다.
lst.delete();
lst.printAll();
System.out.println();
lst.delete();
lst.printAll();
System.out.println();
//루트에 해당하는 값을 삭제하고 출력합니다.
System.out.println(lst.isEmpty());
System.out.println(lst.max());
//lst가 비었는지 여부와 현재 루트에 있는 값을 출력합니다.
}
}- 결과
'자료구조' 카테고리의 다른 글
| [Java] 큐(Queue) 연결 리스트로 구현하기 (0) | 2022.08.01 |
|---|---|
| [Java] 큐(Queue) 배열로 구현하기 (0) | 2022.08.01 |
| [Java] 스택(Stack) 연결 리스트로 구현하기 (0) | 2022.07.30 |
| [Java] 스택(Stack) 배열로 구현하기 (0) | 2022.07.30 |
| [Java] 원형 양방향 연결 리스트 (CircularDoublyLinkedList) 구현하기 (0) | 2022.07.29 |
