안녕하세요😊
오늘은 힙(Heap)에 대해서 포스팅하도록 하겠습니다.
힙(Heap)
힙(Heap) 자료구조는 완전 이진트리를 기초로 하며, 우선순위 큐를 위해 만들어진 자료구조입니다. 힙 자료구조를 사용하면 최댓값과 최솟값을 빠르게 찾을 수 있습니다. 보통 배열에 데이터를 넣고, 최댓값과 최솟값을 찾으려면 O(N)이 걸립니다. 하지만 Heap은 O(logN)만 발생하게 됩니다. 자세한 것은 뒤에서 알아보도록 하겠습니다.
배열을 통해 [최댓값과 최솟값을 구하는 알고리즘]은 아래 링크를 참고해주세요.
[알고리즘] 최솟값, 최댓값 구하기
01. 나열된 수에서 최솟값과 최댓값 구하기 1) 문제 정의 여러 개의 수가 배열에 있을 때 그중 가장 큰 값과 작은 값을 찾고 해당 위치 구하기 단, 반복문은 한번만 사용 2) 수의 예 [10, 55, 23, 2, 79, 1
kang-james.tistory.com
완전 이진트리 특징
1) 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있습니다.
2) 마지막 레벨은 꽉 차 있지 않아도 됩니다.
3) 노드를 삽입할 때 최하단 왼쪽 노드부터 오른쪽 방향으로 차례대로 삽입합니다.
4) 완전 이진트리는 배열을 사용해 효율적으로 표현이 가능합니다.
* 힙과 이진 탐색 트리 비교하기
- 공통점 : 힙과 이진 탐색 트리는 모두 이진트리
- 차이점 :
1) 힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max heap), 또는 작음(Min heap)
2) 이진 탐색 트리는 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 순으로 크기를 가짐
3) 힙은 노드를 추가할 때 마지막 레벨의 왼쪽에서 오른쪽 방향으로 저장
4) 이진 탐색 트리는 탐색을 위한 자료구조, 힙은 최대 / 최솟값 검색을 위한 자료구조
01. 힙(Heap) 구조
- 최대 힙(Max Heap) : 최댓값을 구하기 위한 구조, Root 노드가 가장 큰 값인 형태
- 최소 힙(Min Heap) : 최솟값을 구하기 위한 구조, Root 노드가 가장 작은 값인 형태
02. 힙(Heap) 구현
- 일반적으로 힙 구현 시 배열 자료구조 활용
- 힙을 배열로 구현할 때 0번 인덱스는 null로 두고, 1번 인덱스를 root node로 사용
→ 이유는 힙 구현을 편하게 하기 위해입니다. - 부모 노드 인덱스 번호 = 자식 노드 인덱스 번호 / 2
- 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2
- 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 x 2 + 1
03. 힙(Heap) 코드 작성
예시는 힙의 구조에서 Max Heap으로 구현하도록 하겠습니다.
1) ArrayList를 활용한 Max Heap 구현
import java.util.ArrayList;
import java.util.Collections;
// Max Heap
public class MyHeap {
// ArrayList 활용
public ArrayList<Integer> heapArray = null;
public MyHeap(Integer data) {
heapArray = new ArrayList<Integer>();
heapArray.add(null); // 0번 index는 null
heapArray.add(data); // 새로 생성한 data 1번 index에 추가 - root
}
}
2) 힙에 데이터 삽입하기
먼저 힙에 데이터를 삽입하는 과정을 그림으로 이해해보도록 하겠습니다.
아래 그림과 같이 Max heap에 4를 추가한다고 가정하겠습니다. 힙은 완전 이진트리의 형태를 갖춰야 하기 때문에 4는 6의 오른쪽 자식 노드로 추가될 것입니다. 이처럼 노드는 가장 마지막 level에서 왼쪽에서 오른쪽 방향으로 추가됩니다.
이번에는 해당 힙에 15를 추가하도록 하겠습니다.
15는 8의 왼쪽 자식 노드로 추가가 되는데요. 하지만 15는 8보다 크기 때문에 Max heap의 조건에 어긋나게 됩니다.
이러한 경우에는 15는 8과 비교 한 뒤, (1) 15가 더 크기 때문에 8과 자리를 교체합니다. 이어서 (2) 부모 노드인 9와 비교하고 15와 자리를 교체합니다. 한번 더 (3) 부모 노드인 10과 비교를 진행하는데 역시 15가 크기 때문에 10과 자리를 교체합니다.
이처럼 힙에서 데이터를 추가하면 추가한 노드의 부모 노드와 비교를 진행하고, Max 힙의 경우 자식 노드가 부모 노드보다 크다면, 자리를 교체하면서 조건에 맞게 만듭니다.
* 활용할 참고 클래스 Collections
- Java.util 패키지의 Collections 클래스에서 swap() 메서드를 통해서 배열 내에 데이터끼리 자리를 쉽게 바꿀 수 있습니다.
- swap(스왑) : 두 데이터의 위치를 맞바꾸는 것
ex)
import java.util.Collections;
Collections.swap(List list, int a, int b);
// list 안에 index a와 index b의 위치를 바꿉니다.
2-1) 코드 구현
① 입력한 data를 배열 마지막에 추가하고 부모 노드와 비교합니다.
/**
* 힙에 데이터 삽입하기
*/
public boolean insert(Integer data) {
// insertIdx : 추가 인덱스, parentIdx : 부모 인덱스
Integer insertIdx, parentIdx;
// 배열 안에 아무것도 없을 때
if(heapArray == null) {
// 배열 새로 생성
heapArray = new ArrayList<Integer>();
heapArray.add(null); // 0번 인덱스
heapArray.add(data); // 새로 추가한 데이터를 인덱스 1번에 저장하고, root로 지정
return true; // 생성 성공 true 반환
}
// 배열이 null 이 아닐경우 배열 가장 뒤에 데이터 추가
heapArray.add(data);
insertIdx = this.heapArray.size() - 1; // 방금 데이터 추가한 배열의 마지막 인덱스
// 비교했는데 자식 노드가 부모 노드와 자리를 바꿔야한다면 true
while(this.moveUp(insertIdx)) {
parentIdx = insertIdx / 2;
// Collections 클래스의 swap 메서드를 통해서 자리를 바꿔준다.
Collections.swap(this.heapArray, insertIdx, parentIdx);
insertIdx = parentIdx;
}
return true;
}
② 해당 메서드를 통해서 노드끼리 자리를 바꿔야 하는지 판단합니다.
/**
* 추가 노드가 부모 노드와 교체해야하는지 비교하는 메서드
* @return true / false 만 반환 후 사용한 메서드에서 처리
*/
public boolean moveUp(Integer insertIdx) {
// 새로 추가한 데이터의 index 가 root index 이거나, 배열이 null 인 경우
if(insertIdx <= 1) {
return false;
}
Integer parentIdx = insertIdx / 2; // 부모 노드 인덱스는 자식 노드 인덱스의 1/2 위치함. 소수점은 버림
// 자식 노드가 부모 노드보다 클 경우 true 반환
if(this.heapArray.get(insertIdx) > this.heapArray.get(parentIdx)) {
return true;
} else {
return false;
}
}
3) 힙의 데이터 삭제하기
이번에는 힙 안에 저장되어 있는 데이터를 삭제하는 것을 알아보겠습니다.
힙에서 삭제는 루트 노드의 값을 반환하면서 제거를 하는 것입니다. 제거된 후 빈자리는 힙의 마지막 노드를 가져와서 채우게 됩니다. 그리고 힙을 재구성합니다.
힙 삭제라고 되어있지만, 정확하게는 최댓값, 최솟값을 출력화는 것과 동일합니다.
아래 최대 힙의 예를 보도록 하겠습니다.
① 먼저 삭제를 진행하면 최댓값인 Root 노드의 15를 반환한 후, 제거됩니다. 그리고 힙에서 가장 마지막 노드인 7이 빈자리를 채웁니다.
② root로 올라온 7은 자식 노드와 비교합니다. 여기서 7은 자식 노드보다 작기 때문에 최대 힙 조건에 맞게 자리를 바꿔야 합니다. 이때 바꿀 때는 자식 노드 중 더 큰 값인 10과 교환합니다.
만약 최소 힙이었다면, 자식 노드 중 더 작은 값과 교환하게 됩니다.
③ 이번에도 역시 7은 자식 노드보다 작기 때문에 자식 노드 중 큰 수와 자리를 바꿉니다.
이제 모든 값이 최대 힙의 조건에 부합하기 때문에 더 이상 자리를 바꾸지 않아도 됩니다.
3-1) 코드 구현
① Root의 값은 반환하고, 가장 마지막에 있는 데이터를 Root로 이동시킵니다.
/**
* 힙의 데이터 삭제하기
*
* @return root node의 값 반환
*/
public Integer pop() {
// value = 반환 값
// poppedIdx = 교체된 노드의 인덱스 번호
// leftChildPoppedIdx = 교체된 노드의 왼쪽 자식 노드 인덱스
// rightChildPoppedIdx = 교체된 노드의 오른쪽 자식 노드 인덱스
Integer value, poppedIdx, leftChildPoppedIdx, rightChildPoppedIdx;
// 배열이 null 이면, 반환할 값이 없음
if (this.heapArray == null) {
return null;
} else {
value = this.heapArray.get(1); // root 노드의 값을 반환할 것임
// 힙에서 가장 마지막에 있는 데이터를 빈 자리(root)에 채운다.
this.heapArray.set(1, this.heapArray.get(this.heapArray.size() - 1));
// 힙의 가장 마지막 노드를 root 로 보냈으니 맨 뒤는 제거한다.
this.heapArray.remove(this.heapArray.size() - 1);
poppedIdx = 1;
// moveDown 메서드를 통해서 자식 노드와 부모 노드를 교환해야하는지 판단
while (this.moveDown(poppedIdx)) {
leftChildPoppedIdx = poppedIdx * 2;
rightChildPoppedIdx = poppedIdx * 2 + 1;
// 오른쪽 자식 노드만 없을 때
if(rightChildPoppedIdx >= this.heapArray.size()) {
Collections.swap(heapArray, poppedIdx, leftChildPoppedIdx);
poppedIdx = leftChildPoppedIdx;
// 왼쪽/ 오른쪽 자식 노드 모두 있을 때
} else {
// 왼쪽 자식 노드가 오른쪽 자식 노드보다 클 경우
if(this.heapArray.get(leftChildPoppedIdx) > this.heapArray.get(rightChildPoppedIdx)) {
Collections.swap(heapArray, poppedIdx, leftChildPoppedIdx);
poppedIdx = leftChildPoppedIdx;
} else {
Collections.swap(heapArray, poppedIdx, rightChildPoppedIdx);
poppedIdx = rightChildPoppedIdx;
}
}
}
}
return value;
}② 메서드를 통해서 교체된 노드의 값이 자식 노드와 자리를 바꿔야 하는지 판단합니다.
/**
* 메서드를 통해서 자식 노드와 부모 노드를 교환해야하는지 판단
*
* @return true / false 인지만 반환
*/
public boolean moveDown(Integer poppedIdx) {
Integer leftChildPoppedIdx, rightChildPoppedIdx;
// 왼쪽 자식 노드의 인덱스
leftChildPoppedIdx = poppedIdx * 2;
// 오른쪽 자식 노드의 인덱스
rightChildPoppedIdx = poppedIdx * 2 + 1;
// 왼쪽 자식 노드가 없을 때(자식 노드가 하나도 없을 때)
if (leftChildPoppedIdx >= this.heapArray.size()) {
return false;
// 오른쪽 자식 노드가 없을 때
} else if (rightChildPoppedIdx >= this.heapArray.size()) {
// 교체된 노드의 값보다 교체된 노드의 왼쪽 자식 노드의 값이 클 경우
if (this.heapArray.get(poppedIdx) < this.heapArray.get(leftChildPoppedIdx)) {
return true;
} else {
return false;
}
// 왼쪽 / 오른쪽 자식 노드가 모두 있을 때
} else {
// 왼쪽 자식 노드가 오른쪽 자식 노드보다 클 때
if (this.heapArray.get(leftChildPoppedIdx) > this.heapArray.get(rightChildPoppedIdx)) {
// 교체된 노드의 값보다 교체된 노드의 왼쪽 자식 노드의 값이 클 경우 true 반환
if (this.heapArray.get(poppedIdx) < this.heapArray.get(leftChildPoppedIdx)) {
return true;
} else {
return false;
}
// 오른쪽 자식 노드가 왼쪽 자식 노드보다 클 때
} else {
// 교체된 노드의 값보다 교체된 노드의 오른쪽 자식 노드의 값이 클 경우 true 반환
if (this.heapArray.get(poppedIdx) < this.heapArray.get(rightChildPoppedIdx)) {
return true;
} else {
return false;
}
}
}
}
위에 작성한 코드를 실행하면 아래와 같은 결과를 알 수 있습니다.
자세한 내용은 아래 Github에서 확인해주세요.
https://github.com/Si-Hyeak-KANG/java_algorithm/blob/master/src/dataStructureSudy/base01/MyHeap.java
GitHub - Si-Hyeak-KANG/java_algorithm: JAVA를 활용한 코딩 테스트 공부
JAVA를 활용한 코딩 테스트 공부 . Contribute to Si-Hyeak-KANG/java_algorithm development by creating an account on GitHub.
github.com
코드가 굉장히 복잡했지만, 이번 포스팅에서는 모두 게시해봤습니다.
이렇게 [배열, 큐, 스택, 연결 리스트, 트리, 힙]까지 정리를 마쳤습니다. 이번에 시간이 되어 자료구조들을 정리할 수 있었는데요. 많은 개발자들에게 자료구조를 직접 구현해보라고 추천하고 싶습니다.😊 개인적으로 저는 자료구조의 원리를 확실하게 알 수 있어서 좋았고, 무엇보다 너무 재밌었습니다.
다음 포스팅부터는 알고리즘으로 인사드리도록 하겠습니다~!
'개발 > DS&Algorithms' 카테고리의 다른 글
| [알고리즘] 선택 정렬(Selection sort) 알아보기 (3) | 2022.04.25 |
|---|---|
| [알고리즘] 버블 정렬(bubble sort) 알아보기 (16) | 2022.04.21 |
| [자료구조] 트리(Tree) 알아보기 (feat.이진 탐색 트리) (4) | 2022.04.13 |
| [자료구조] 해시(HASH) 알아보기 (2) | 2022.04.07 |
| [자료구조] 연결 리스트(Linked List) 알아보기 (6) | 2022.04.01 |
