자바를 통한 힙에서 데이터 삽입 구현
자바에서 구현한 힙 트리 데이터 삽입 코드는 다음과 같다.
- Heap.java
// 힙 트리 데이터 추가
public boolean insert(int data) {
// 방어 코드 : 힙 배열에 아무 데이터도 들어가 있지 않은 상태에서
// 메소드가 수행되는 경우를 대비하여 리스트에 데이터 값을 적재해주는 코드를 작성해준다.
if(this.heapArray.size() == 0) {
this.heapArray.add(null);
this.heapArray.add(data);
return true;
}
// ArrayList 에서 add 라는 메소드 자체가 리스트의 가장 마지막 부분에
// 데이터를 추가해주는 것이기 때문에 힙 트리의 마지막 요소에 데이터를 추가해주기 위해
// 굳이 추가적인 로직을 더 작성해줄 필요가 없다.
// 연결리스트를 구조를 직접 구현하면서 트리를 만들고 있는것이 아니라, ArrayList 를 통해
// 트리를 만들고 있기 때문에 얻을 수 있는 장점이다.
this.heapArray.add(data);
// 삽입한 데이터가 부모 노드보다 값이 클 경우의 로직을 작성해준다.
// 마지막으로 삽입한 데이터의 인덱스를 알아낸다.
int insertedIdx = this.heapArray.size() - 1;
while(moveUp(insertedIdx)) {
// moveUp 메소드 실행결과 true 를 반환하면 계속 반복문을 수행한다.
// 삽입된 데이터의 노드의 부모 노드 인덱스를 알아낸다.
int parentIdx = insertedIdx / 2;
// 부모 노드와 삽입된 데이터 노드의 위치를 바꿔준다.
int temp = this.heapArray.get(insertedIdx);
this.heapArray.set(insertedIdx, this.heapArray.get(parentIdx));
this.heapArray.set(parentIdx, temp);
insertedIdx = parentIdx;
}
return true;
}
// 삽입된 데이터가 부모 노드보다 큰지 작은지에 대한 검증 결과를 반환해주는 메소드를 작성해준다.
private boolean moveUp(int insertedIdx) {
// 삽입된 데이터가 루트 노드까지 올라갔을 경우
// 더 이상 데이터 비교 및 위치 스왑 작업을 해줄 필요가 없다.
if(insertedIdx <= 1)
return false;
int parentIdx = insertedIdx / 2;
// 삽입된 노드의 데이터가 부모 노드의 데이터 보다 큰 경우
// true 를 반환시켜 반복문을 수행시킨다.
if(this.heapArray.get(insertedIdx) > this.heapArray.get(parentIdx)) {
return true;
}
else
return false;
}- insert 메소드 시작 부에서 힙 트리가 없을 때를 대비하여 방어코드를 작성하였다.
- 방어코드 이후엔 파라미터로 넘어온 data 값을 heapArray 에 add 메소드를 통해 삽입 해주었는데
단순히 add 메소드를 사용하는 것 만으로 힙 트리의 가장 마지막에 데이터를 추가해줄 수 있다.
(add 메소드 자체가 데이터를 해당 자료구조의 가장 마지막에 추가하는 기능을 제공해준다.)
- 마지막으로 삽입한 데이터의 인덱스 위치를 알아낸 다음 moveUp 메소드의 실행결과에 따라 반복문을 수행하거나 종료시킨다.
- moveUp 메소드는 파라미터로 넘어온 삽입된 노드에 대한 인덱스를 기준으로 해당 노드가 부모 노드 보다 클 경우 true 를 반환시켜 반복문을 계속 수행시키고, 그렇지 않을 경우 반복문을 종료 시키는 동작을 수행한다.
- 만약 삽입된 노드의 데이터 값이 부모 노드의 데이터값보다 클 경우 반복문 내부에서 부모 노드와 삽입된 노드간의 위치를 교체해준다.
자바를 통한 힙에서 데이터 삭제 구현
자바에서 구현한 힙 트리 데이터 삭제 코드는 다음과 같다.
- Heap.java
// 힙 트리 데이터 삭제 - 최대값(Root Node)
public int pop() {
// Root Node 데이터 적재
int returnedData = this.heapArray.get(1);
// 힙에 마지막으로 들어온 데이터를 Root Node 로 올려준다.
this.heapArray.set(1, this.heapArray.get(this.heapArray.size()-1));
// 마지막으로 힙 트리에 들어온 노드가 있던 위치의 노드를 삭제헤준다.
this.heapArray.remove(this.heapArray.size()-1);
// Root Node 와 자식 노드간 위치 변경이 필요한 경우를 위해
// Root Node 의 인덱스를 따로 적재해준다.
int popedIdx = 1;
// moveDown 메소드 실행결과 true 를 반환하면 계속 반복문을 수행한다.
while(moveDown(popedIdx)) {
int leftChildIdx = popedIdx * 2;
int rightChildIdx = popedIdx * 2 + 1;
// Leaf Node 인 경우 moveDown 메소드의 반환값이 false 가 되어
// 반복문이 수행되지 않으므로 고려하지 않는다.
// 어떤 로직에 의해 moveDown 메소드가 true 를 반환했는지 모르기 때문에
// 반복문에서 각 로직 별로 코드를 다시 작성해준다.
// 오른쪽 자식 노드만 없을 경우(왼쪽 자식 노드만 있을 경우)
if(rightChildIdx >= this.heapArray.size()) {
// 왼쪽 노드의 값이 부모 노드보다 큰 경우 위치를 바꿔준다.
if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIdx)) {
int temp = this.heapArray.get(leftChildIdx);
this.heapArray.set(leftChildIdx, this.heapArray.get(popedIdx));
this.heapArray.set(popedIdx, temp);
popedIdx = leftChildIdx;
}
}
// 왼쪽, 오른쪽 자식 노드가 모두 존재할 경우
else {
if(this.heapArray.get(leftChildIdx) > this.heapArray.get(rightChildIdx)) {
if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIdx)) {
int temp = this.heapArray.get(leftChildIdx);
this.heapArray.set(leftChildIdx, this.heapArray.get(popedIdx));
this.heapArray.set(popedIdx, temp);
popedIdx = leftChildIdx;
}
}
else {
if(this.heapArray.get(popedIdx) < this.heapArray.get(rightChildIdx)) {
int temp = this.heapArray.get(rightChildIdx);
this.heapArray.set(rightChildIdx, this.heapArray.get(popedIdx));
this.heapArray.set(popedIdx, temp);
popedIdx = rightChildIdx;
}
}
}
}
return returnedData;
}
// 자식 노드가 부모 노드보다 큰지 작은지에 대한 검증 결과를 반환해주는 메소드를 작성해준다.
private boolean moveDown(int popedIdx) {
// 왼쪽 자식 노드와 오른쪽 자식 노드의 인덱스를 알아낸다.
int leftChildIndex = popedIdx * 2;
int rightChildIndex = popedIdx * 2 + 1;
// case 1 : 왼쪽 자식노드 조차 존재하지 않을 때(Child Node 를 가지고 있지 않을 때(Leaf Node))
// 왼쪽 자식 노드 인덱스에 대한 계산결과가 리스트의 길이를 넘어가는 경우
if(leftChildIndex >= this.heapArray.size())
return false;
// case 2 : 오른쪽 자식노드만 존재하지 않을 때(왼쪽 자식 노드가 존재함)
// 오른쪽 자식 노드 인덱스에 대한 계산결과가 리스트의 길이를 넘어가는 경우
else if(rightChildIndex >= this.heapArray.size()) {
// 왼쪽 자식 노드가 부모 노드보다 클 경우 위치를 바꿔주어야 한다.
if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIndex))
return true;
else
return false;
}
// case 3 : 두 개의 자식 노드를 모두 가지고 있을 때
else {
// 왼쪽 자식 노드가 오른쪽 자식 노드보다 큰 경우
if(this.heapArray.get(leftChildIndex) > this.heapArray.get(rightChildIndex)) {
// 왼쪽 자식 노드가 부모 노드 보다 큰 경우 위치를 바꿔주어야 한다.
if(this.heapArray.get(popedIdx) < this.heapArray.get(leftChildIndex))
return true;
else
return false;
}
// 오른쪽 자식 노드가 왼쪽 자식 노드보다 크거나 같을 경우
else {
// 오른쪽 자식 노드가 부모 노드보다 큰 경우 위치를 바꿔주어야 한다.
if(this.heapArray.get(popedIdx) < this.heapArray.get(rightChildIndex))
return true;
else
return false;
}
}
}- 우선 힙 트리에서 삭제시킬 최대값(Root Node) 를 반환값에 적재시키고, 마지막으로 들어온 데이터를 Root Node 의 위치로 올려준다.
- 마지막으로 힙 트리에 들어온 노드가 있던 위치를 삭제해주고 난 다음, Root Node 와 Child Node 간 위치 변경이 필요한 경우를 위해 Root Node 의 인덱스 번호를 따로 적재해둔다.
- moveDown 메소드의 반환값이 true 인 동안 반복문을 수행한다.
- moveDown 메소든 부모 노드와 자식 노드간 위치 변경이 필요한 지를 판단해주는 메소드 이며, 부모 노드의 자식이 없을 경우, 부모 노드가 왼쪽 노드만 자식 노드로 가지고 있을 경우, 부모 노드가 왼쪽, 오른쪽 자식 노드를 모두 가지고 있을 경우를 나눠 위치 변경 여부를 판별한다.
- 자식노드가 존재하지 않을 경우 해당 노드가 Leaf Node 란 뜻으로, 더 이상 위치 변경의 여지가 없기 때문에 false 를 리턴한다.
- 자식노드가 왼쪽 노드 하나만 존재할 경우, 왼쪽 자식 노드와 부모 노드간 데이터를 비교하여 왼쪽 자식 노드의 데이터가 더 클 경우 위치 변경을 해야하므로 true 를 반환해주고 그렇지 않을 경우 false 를 반환해준다.
- 양쪽 노드가 다 있을 경우 어느쪽 노드의 데이터 값이 더 큰지 판별한 다음, 왼쪽 또는 오른쪽 노드가 부모 노드보다 크다면 위치 변경이 필요하므로 true 를 반환해주고, 그렇지 않으면 false 를 반환해준다.
- moveDown 메소드에서 true 가 반환되어 반복문이 수행될 경우 다음과 같이 동작한다.
- 해당 노드가 Leaf Node 인 경우 애초에 fasle 가 반환되어 반복문이 종료되므로 해당 경우의 로직은 고려하지 않는다.
- 해당 노드가 자식 노드를 왼쪽 노드 하나만 가지고 있을 경우, 왼쪽 노드가 부모 노드보다 값이 크다면 위치를 변경해준다.
- 해당 노드가 양쪽 노드를 모두 가지고 있을 경우, 둘 중 어느 노드가 더 큰지를 판별하여 해당 자식 노드와 부모 노드의 데이터 값을 비교해 준 후, 자식 노드의 값이 부모 노드의 값보다 크다면 노드 간의 위치를 변경해준다.
* 구현된 코드에 대한 시험 코드는 다음과 같다.
- Heap_main.java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.List;
public class Heap_main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
bw.write("데이터를 입력하세요 : ");
bw.flush();
int number = Integer.parseInt(br.readLine());
Heap heap = new Heap(number);
bw.write("데이터가 정상적으로 입력 되었습니다.\n");
bw.write("힙 트리가 생성 되었습니다.\n\n");
while(true) {
bw.write("메뉴를 선택하세요\n");
bw.write("1. 데이터 추가\n");
bw.write("2. 데이터 삭제\n");
bw.write("3. 힙 트리 전체 출력\n");
bw.write("4. 프로그램 종료\n");
bw.write("번호를 입력하세요(숫자) : ");
bw.flush();
int option = Integer.parseInt(br.readLine());
if(option == 4) {
bw.write("프로그램이 종료됩니다.\n");
bw.flush();
break;
}
else if(option == 1) {
bw.write("\n데이터를 입력하세요 : ");
bw.flush();
int data = Integer.parseInt(br.readLine());
if(heap.insert(data)) {
bw.write("데이터가 정상적으로 삽입 되었습니다.\n\n");
bw.flush();
}
}
else if(option == 2) {
int pop = heap.pop();
bw.write("\n데이터가 정상적으로 삭제 되었습니다.\n");
bw.write("삭제된 데이터 : " + pop + "\n\n");
bw.flush();
}
else if(option == 3) {
List<Integer> heapTree = heap.getHeapArray();
if(heapTree != null) {
bw.write("\n힙 트리 전체를 출력합니다.\n");
heapTree.stream().forEach(x -> {
try {
bw.write(x + " ");
bw.flush();
} catch (IOException e) {
e.printStackTrace();
}
});
bw.write("\n\n");
bw.flush();
}
else {
bw.write("\n힙 트리가 존재하지 않습니다.\n");
bw.write("힙 트리를 만들어주세요\n\n");
bw.flush();
}
}
}
}
}
힙의 시간 복잡도
- depth(트리의 높이) 를 h 라고 표기한다.
- n 개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제 시, 최악의 경우 Root Node 에서 Leaf Node 까지 비교해야 하므로 h = log2n 에 가깝다.
- 그러므로 시간 복잡도는 O(log n) 이다.(마지막에 삽입된 데이터가 최대 힙 기준에서 최소값에 해당할 경우)
* 참고 : 빅오 표기법에서 log n 에서의 log 의 밑은 10이 아니라 2이다.
* 한번 실행 시 마다 50% 의 실행할 수도 있는 명령을 제거한다는 의미이다.
* 즉, 50% 의 실행시간을 단축시킬 수 있다는 것을 의미한다.
'자료구조 및 알고리즘 > 자료구조' 카테고리의 다른 글
| [자료구조] 자바 에서의 힙(Heap) #1 (0) | 2021.11.30 |
|---|---|
| [자료구조] 자바 에서의 트리 #2 (0) | 2021.11.28 |
| [자료구조] 자바 에서의 트리 #1 (0) | 2021.11.28 |
| [자료구조] 자바에서의 해쉬 테이블과 충돌 문제 해결 (0) | 2021.11.25 |
| [자료구조] - 자바로 연결 리스트를 구현해보자. #2 (0) | 2021.11.25 |
