힙(Heap)
완전 이진 트리 형태(마지막 레벨 빼고 다 차있는 형태)
-> 예를들어, 0레벨과 1레벨에 노드가 가득 차있고, 2레벨에 맨왼쪽 노드 한개만 차있다면 이는 완전 이진트리 지만, 맨 오른쪽 노드 한개만 차있다면 이는 완전 이진트리가 아님!
-> 좌측부터 데이터가 차있어야 완전 이진 트리
다른 트리들과 다르게 중복 값 허용, 반 정렬 상태(최소힙은 루트가 가장 작은 값, 최대힙은 루트노드가 가장 큰 값)
-> 형제 노드에 대한 크기의 우선순위는 없음
최소값이나 최대값을 빠르게 찾아내는데 유용한 자료구조
최소 힙(Min Heap)
부모 노드의 키가 자식 노드의 키보다 작거나 같음
최대 힙(Max Heap)
최소 힙 삽입
우선 트리의 가장 끝 위치에 데이터를 삽입
-> 이후 부모 노드와 키 비교한 후 작을 경우 부모 자리와 교체(반복)
최소 힙 삭제
최상위 노드 반환 및 삭제
이후 가장 마지막 위치의 노드를 최상의 노드로 위치 시키고
-> 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 (반복)
ArrayList로 최소 Heap 구현
class MinHeap{
ArrayList<Integer> heap;
public MinHeap(){
heap = new ArrayList<>();
this.heap.add(0); // 인덱스 기준으로 1번부터 시작할 수 있도록
}
public void insert(int data){
heap.add(data);
// 데이터를 넣은 후 자신의 부모와 키값을 비교(작으면 위로)
int cur = heap.size() - 1;
while(cur > 1 && heap.get(cur / 2) > heap.get(cur)){
int parent = heap.get(cur/2);
heap.set(cur/2, data);
heap.set(cur, parent);
cur /= 2;
}
}
public Integer delete(){
if(heap.size() == 1){
System.out.println("Heap is Empty!");
return null;
}
int target = heap.get(1); // 가장 상위 노드
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int cur = 1;
while(true){
int leftIdx = cur * 2;
int rightIdx = cur * 2 + 1;
int targetIdx = -1;
if(rightIdx < heap.size()){
// 오른쪽 자식 노드가 있는 경우
targetIdx = heap.get(leftIdx) < heap.get(rightIdx) ? leftIdx : rightIdx;
}else if(leftIdx < heap.size()){
// 자식이 하나인 경우
targetIdx = cur * 2;
}else{
break;
}
if(heap.get(cur) < heap.get(targetIdx)){
break;
}else{
int parentVal = heap.get(cur);
heap.set(cur, heap.get(targetIdx));
heap.set(targetIdx, parentVal);
cur = targetIdx;
}
}
return target;
}
public void printTree(){
for (int i = 1; i < heap.size(); i++) {
System.out.print(this.heap.get(i) + " ");
}
System.out.println();
}
}ArrayList로 최대 Heap 구현
max 힙을 구현하는 경우 위 코드의 while 조건에 heap.get(cur / 2) < heap.get(cur)로 바꿈
delete 쪽에서는 삼항 연산자의 부호를 바꿔주고 마지막 if문의 조건 교체
연습 문제
문제 1
// 최소 힙에서 특정 값을 변경하는 코드 작성하기
// 특정 값이 여러개라면 모두 바꾸기
public class Practice1 {
public static void solution(MinHeap minHeap, int from, int to){
for(int i = 0; i < minHeap.heap.size(); i++){
if(minHeap.heap.get(i) == from){
minHeap.heap.set(i, to);
moveUp(minHeap, i);
moveDown(minHeap,i);
}
}
}
public static void moveUp(MinHeap minHeap, int idx){
int cur = idx;
while(cur > 1 && minHeap.heap.get(cur / 2) > minHeap.heap.get(cur)){
int parentVal = minHeap.heap.get(cur / 2);
minHeap.heap.set(cur / 2, minHeap.heap.get(cur));
minHeap.heap.set(cur, parentVal);
cur /= 2;
}
}
public static void moveDown(MinHeap minHeap, int idx){
int cur = idx;
while(true){
int left = cur * 2;
int right = cur * 2 + 1;
int targetIdx = -1;
if(right < minHeap.heap.size()){
targetIdx = minHeap.heap.get(left) < minHeap.heap.get(right)? left : right;
}else if(left < minHeap.heap.size()){
targetIdx = left;
}else{
break;
}
if(minHeap.heap.get(cur) < minHeap.heap.get(targetIdx)){
break;
}else{
int parentVal = minHeap.heap.get(cur);
minHeap.heap.set(cur, minHeap.heap.get(targetIdx));
minHeap.heap.set(targetIdx, parentVal);
cur = targetIdx;
}
}
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(30);minHeap.insert(40);minHeap.insert(10);
minHeap.insert(50);minHeap.insert(60);minHeap.insert(70);
minHeap.insert(20); minHeap.insert(30);
System.out.println("== 데이터 변경 전 ==");
minHeap.printTree();
System.out.println("== 데이터 변경 후 == ");
solution(minHeap, 30, 100);
minHeap.printTree();
solution(minHeap, 60, 1);
minHeap.printTree();
}
}
문제 2
// 최소 힙, 최대 힙을 이용하여 데이터를 오름차순, 내림차순으로 출력하기
public class Practice2 {
public static void solution(MinHeap minHeap) {
MaxHeap maxHeap = new MaxHeap();
System.out.print("오름차순 : ");
while(minHeap.heap.size() != 1){
int data = minHeap.delete();
System.out.print(data + " ");
maxHeap.insert(data);
}
System.out.println();
System.out.println("내림차순 : ");
while(maxHeap.heap.size() != 1){
System.out.print(maxHeap.delete() + " ");
}
System.out.println();
}
public static void main(String[] args) {
MinHeap minHeap = new MinHeap();
minHeap.insert(30);minHeap.insert(40);
minHeap.insert(10);minHeap.insert(50);
minHeap.insert(60);minHeap.insert(70);
minHeap.insert(20);minHeap.insert(30);
solution(minHeap);
}
}문제 3
// 정수들을 힙 자료구조에 추가하고 n번 삭제 후 절대값이 큰 값부터 출력하세요.
// 입력 : 3 0 -2 -5 9 6 -11 20 -30
// 삭제 횟수 : 1
// 출력 : 20, -11, 9, 6, -5, 3, -2, 0
import java.util.ArrayList;
import java.util.stream.IntStream;
class Num{
int val; // 절댓값 넣기
boolean isMinus;
public Num(int val){
this.isMinus = val < 0 ? true:false;
this.val = Math.abs(val);
}
}
class MaxHeap2{
ArrayList<Num> heap;
MaxHeap2(){
this.heap = new ArrayList<>();
this.heap.add(new Num(0));
}
public void insert(int data){
heap.add(new Num(data));
int cur = heap.size() - 1;
while(cur > 1 && heap.get(cur / 2).val < heap.get(cur).val){
Num parent = heap.get(cur / 2);
heap.set(cur/2, heap.get(cur));
heap.set(cur, parent);
cur /= 2;
}
}
public Num delete(){
if(heap.size() == 1){
System.out.println("Heap is Empty!");
return null;
}
Num target = heap.get(1); // 가장 상위 노드
heap.set(1, heap.get(heap.size() - 1));
heap.remove(heap.size() - 1);
int cur = 1;
while(true){
int leftIdx = 2 * cur;
int rightIdx = 2 * cur + 1;
int targetIdx = -1;
if(rightIdx < heap.size()){
targetIdx = heap.get(leftIdx).val > heap.get(rightIdx).val? leftIdx: rightIdx;
}else if(leftIdx < heap.size()){
targetIdx = cur * 2;
}else{
break;
}
if(heap.get(cur).val > heap.get(targetIdx).val){
break;
}else{
Num parentVal = heap.get(cur);
heap.set(cur, heap.get(targetIdx));
heap.set(targetIdx, parentVal);
cur = targetIdx;
}
}
return target;
}
public void printTree(){
for(int i = 1; i < heap.size(); i++){
System.out.print(heap.get(i) + " ");
}
System.out.println();
}
}
public class Practice3 {
public static void solution(int[] nums, int deleteCnt){
MaxHeap2 maxHeap = new MaxHeap2();
IntStream.of(nums).forEach(x -> maxHeap.insert(x));
int cnt = 0;
while(maxHeap.heap.size() != 1){
Num cur = maxHeap.delete();
if(cnt++ < deleteCnt){
continue;
}
int originVal = cur.isMinus ? cur.val * -1 : cur.val;
System.out.print(originVal + " ");
}
System.out.println();
}
public static void main(String[] args) {
int nums[] = {3, 0, -2, -5, 9, 6, -11, 20, -30};
int deleteCnt = 1;
solution(nums, deleteCnt);
}
}
Journey for Backend Developer