[Java] 힙(Heap)

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

위 문제를 풀면서 대학교 2학년 때 배웠던 힙이 기억이 안 나서 공부하게 되었다.

 

우선 힙(Heap)에 대해서 알아보자.

 

힙(Heap)이란?

힙은 '최소값 혹은 최댓값을 빠르게 찾기 위한 완전 이진트리 형태로 만들어진 자료구조'라고 정의할 수 있다.

 

우선 '이진 트리' 구조로는 힙을 구현할 수 없다.

 

힙의 중요한 모토는 

 

• 최소 힙 - 부모 노드가 반드시 자식 노드보다 작아야 한다.
• 최대 힙 - 부모 노드가 반드시 자식 노드보다 커야 한다.
• 힙 구조는 값이 쌓인 구조이다.

위의 조건을 반드시 충족해야 하기 때문에 단순 이진트리는 힙 자료구조를 구현하기에 좋지 않다.

 

그러므로 최소 완전이진트리 자료구조여야 한다.

 

---

앞서 말했듯

최소 힙은 '부모 노드가 자식노드보다 작은 구조'

최대 힙은 '부모 노드가 자식노드보다 큰 구조' 형태이다.

 

 

최소 힙을 구현하는 가정하에 알아보도록 하자.

 

구현 방법은 다음의 순서를 따른다.

 

1. 가장 마지막 노드 자리에 넣고자 하는 값을 삽입한다.

 

7 삽입

2. 삽입한 노드와 부모노드의 값을 비교한다.

3. 부모노드값이 더 크다면 해당 노드와 자리를 바꾼다.

 

4. 해당 규칙이 '최소 힙'을 만족할 때까지 2번, 3번을 반복한다.

 

---

배열로 구현하기

힙은 반드시 완전 이진트리를 만족해야 한다.

 

즉 모든 값이 빠진 자리 없이 순서대로 나열된다는 뜻이다.

 

그렇다면 완전 이진트리를 선형구조인 1차원 배열로 구현하는 것이 가능해진다.

 

0번 인덱스는 빈 값(혹은 0)으로 두고 1번 인덱스가 root이며 BFS 읽기 방법으로 인덱스 번호를 매기면

 

위의 배열과 같이 표시할 수 있다.

 

즉 arr[n]의 왼쪽 자식 노드는 arr[n*2], 오른쪽 자식 노드는 arr[n*2 + 1]로 표시할 수 있다.

 

1. Heap 구조 초기화

public class Main {
	
	static List<Integer> heap;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		heap = new ArrayList<Integer>();
		heap.add(0); //0번 인덱스는 0으로 초기화
		
		while(true) {
			int a = Integer.parseInt(br.readLine());
			if(a == -1) { //-1  종료
				System.out.println("end");
				break;
			} else if(a == 0) { // 0 입력시 최소 힙 출력
				pop();
			} else { //최소 힙 추가
				add(a);
				System.out.println(heap);
			}
		}
	}
}

우선 0번 인덱스는 0으로 초기화한 후

 

각 값을 입력받아서

-1은 종료

0은 출력 및 삭제

그 외의 정수는 힙 추가하였다.

 

2. 힙 추가

private static void add(int val) {
    // TODO Auto-generated method stub
    heap.add(val); //맨 뒤에 값 추가

    int position = heap.size() - 1; //맨 뒤 위치

    while(position > 1 && heap.get(position/2) > heap.get(position)) { 
        //root 위치가 아니며, 추가한 값이 부모 노드보다 크면 위치 변경

        int parent = heap.get(position/2); //부모 노드 값
        heap.set(position/2, val); //부모 노드 위치에 추가한 값으로 변경
        heap.set(position, parent); //값이 더 큰 부모노드 값을 자식노드로

        position /= 2; //현재 위치 갱신
    }
}

 

2. 최소 힙 출력 및 삭제

 

private static void pop() {
    // TODO Auto-generated method stub
    if(heap.size() - 1 < 1 ) {
        System.out.println("0"); //힙이 비어있으면 0 출력
        return;
    }

    int delete_item = heap.get(1); //가장 최소값인 루트 노드를 추출
    System.out.println(delete_item); //최소 값 출력

    heap.set(1, heap.get(heap.size() - 1)); //마지막 노드를 root로 변경
    heap.remove(heap.size() - 1); //마지막 노드 삭제

    int position = 1; //root 노드 부터 힙 정렬 재시작

    while( position*2 < heap.size() ) { 
        //힙 크기보다 위치 *2가 작다면 일단 왼쪽 자식 노드가 있다는 뜻으로 값 비교 진행

        int min_val = heap.get(position*2); //왼쪽 자식 노드 값
        int min_pos = position*2; //왼쪽 자식 노드 위치

        if( position*2+1 < heap.size() && min_val > heap.get(position*2+1) ) {
            //오른쪽 자식 노드가 존재하고
            //오른쪽 자식 노드가 왼쪽 자식노드보다 작으면
            min_val = heap.get(position*2+1);
            min_pos = position*2+1;
            //최소 값의 값과 위치를 오른쪽으로 변경
        }

        if(min_val > heap.get(position)) {
            break; //이미 자식노드가 현재 위치 노드보다 크면 (최소힙) 힙 정렬 종료
        }

        // 부모 노드가 자식노드보다 값이 크면 값 변경
        int tmp = heap.get(position);
        heap.set(position, heap.get(min_pos)); //값이 작은 자식노드를 부모 노드로
        heap.set(min_pos, tmp); // 값이 큰 부모 노드를 자식노드로 변경
    }
}

 

 

3. 전체 코드 및 결과

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
	
	static List<Integer> heap;

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
				
		heap = new ArrayList<Integer>();
		heap.add(0); //0번 인덱스는 0으로 초기화
		
		while(true) {
			int a = Integer.parseInt(br.readLine());
			if(a == -1) { //-1  종료
				System.out.println("end");
				break;
			} else if(a == 0) { // 0 입력시 최소 힙 출력
				pop();
			} else { //최소 힙 추가
				add(a);
				System.out.println(heap);
			}
		}
	}

	private static void pop() {
		// TODO Auto-generated method stub
		if(heap.size() - 1 < 1 ) {
			System.out.println("0"); //힙이 비어있으면 0 출력
			return;
		}
		
		int delete_item = heap.get(1); //가장 최소값인 루트 노드를 추출
		System.out.println(delete_item); //최소 값 출력
		
		heap.set(1, heap.get(heap.size() - 1)); //마지막 노드를 root로 변경
		heap.remove(heap.size() - 1); //마지막 노드 삭제
		
		int position = 1; //root 노드 부터 힙 정렬 재시작
		
		while( position*2 < heap.size() ) { 
			//힙 크기보다 위치 *2가 작다면 일단 왼쪽 자식 노드가 있다는 뜻으로 값 비교 진행
			
			int min_val = heap.get(position*2); //왼쪽 자식 노드 값
			int min_pos = position*2; //왼쪽 자식 노드 위치
			
			if( position*2+1 < heap.size() && min_val > heap.get(position*2+1) ) {
				//오른쪽 자식 노드가 존재하고
				//오른쪽 자식 노드가 왼쪽 자식노드보다 작으면
				min_val = heap.get(position*2+1);
				min_pos = position*2+1;
				//최소 값의 값과 위치를 오른쪽으로 변경
			}
			
			if(min_val > heap.get(position)) {
				break; //이미 자식노드가 현재 위치 노드보다 크면 (최소힙) 힙 정렬 종료
			}
			
			// 부모 노드가 자식노드보다 값이 크면 값 변경
			int tmp = heap.get(position);
			heap.set(position, heap.get(min_pos)); //값이 작은 자식노드를 부모 노드로
			heap.set(min_pos, tmp); // 값이 큰 부모 노드를 자식노드로 변경
		}
	}

	private static void add(int val) {
		// TODO Auto-generated method stub
		heap.add(val); //맨 뒤에 값 추가
		
		int position = heap.size() - 1; //맨 뒤 위치
		
		while(position > 1 && heap.get(position/2) > heap.get(position)) { 
			//root 위치가 아니며, 추가한 값이 부모 노드보다 크면 위치 변경
			
			int parent = heap.get(position/2); //부모 노드 값
			heap.set(position/2, val); //부모 노드 위치에 추가한 값으로 변경
			heap.set(position, parent); //값이 더 큰 부모노드 값을 자식노드로
			
			position /= 2; //현재 위치 갱신
		}
	}
	
	
}

 

 

 

5 4 3 2 1  순 입력하여 heap 구조를 보여주고

 

0 0 0 0 0 입력하여 각 작은 값이 나오는지 확인한다.

 

최대 힙은 위와 반대로 적용하면 된다.

 

 

---

Ref

 

https://go-coding.tistory.com/25

https://namu.wiki/w/%ED%9E%99%20%ED%8A%B8%EB%A6%AC

https://st-lab.tistory.com/205