[자료구조/Java] 힙(Heap) 구현

 

시간이 지나면 자꾸 까먹는다.. 그래서 다시 정리해봐야겠다

 

자료구조의 핵심 중 하나인 힙(Heap)에 대해 알아보자

 

 

힙(Heap)

---

완전 이진트리의 일종이다.

 

반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용된다.

 

삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다.

 

보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이기 때문이다.

 

 

힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다.

 

이를 통해 여러 값 중에서 최소 값이나 최대 값을 빨리 찾을 때 유용하게 이용할 수 있다.

 

 

힙 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다.

 

1번째 인덱스부터 시작하면, 해당 인덱스의 자식 노드는 각각 *2, *2+1로 나타낼 수 있다.

(1번째 인덱스의 자식노드는 1*2, 1*2+1이다.)

 

마찬가지로 자식노드 위치(N)에서 부모노드 인덱스는 N/2로 표현할 수 있다.

 

우선순위 큐를 이용해서 문제를 풀어야 할 때, B형 시험처럼 라이브러리 사용이 불가능할 때 힙을 구현해야 한다.

Java로 최소 힙과 최대 힙을 구현한 코드는 아래와 같다.

 

최소힙 삭제 진행연산 전개

[delete 메소드] 
// heap.size가 비어있으면 리턴
// 부모 노드값 저장
// 부모 노드에 맨 마지막 값 저장
// 맨 마지막 값 삭제
// pos 값 1로 선언 (첫 부모 인덱스)
// while문에서 왼쪽 자식으로 시작 (pos*2)가 heap 사이즈보다 작은 동안
// min = 왼쪽 자식 노드 값
// minPos = 왼쪽 자식 노드 인덱스
// 오른쪽 자식 노드가 있는지 여부 확인. 오른쪽 노드가 더 작으면 min,minPos 오른쪽 노드로 갱신
// min이 부모보다 더 크면 바꿀 필요 없으므로 종료
// 부모와 자식 노드 교환

 

 

최소힙(MinHeap)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class MinHeap {
    
    public static class minHeap {
        
        private ArrayList<Integer> heap;
        
        // 힙 생성자
        public minHeap() {
            heap = new ArrayList<>();
            heap.add(0); // 인덱스 0 채우기 (1부터 시작하기 위함)
        }
        
        // 삽입
        public void insert(int val) {
            heap.add(val);
            int p = heap.size() - 1;
            
            // 힙 사이즈 - 1이 1보다 작아질 때까지 진행 -> root로 이동
            while(p > 1 && heap.get(p / 2) > heap.get(p)) {
                System.out.println("swap");
                // 부모보다 자식 노드가 더 작으면 바꿔야 함 (최소힙)
                int tmp = heap.get(p/2);
                heap.set(p/2, heap.get(p));
                heap.set(p, tmp);
                
                p = p / 2; // p는 부모 값으로 변경 (부모 노드 인덱스로 이동)
            }
        }
        
        // 삭제
        public int delete() {
            
            // 힙 사이즈 - 1이 1보다 작으면 0 리턴
            if(heap.size()-1 < 1) {
                return 0;
            }
            
            // 삭제할 노드는 루트 노드임
            int deleteItem = heap.get(1);
            
            // root에 가장 마지막 값 넣고 마지막 값 삭제
            heap.set(1, heap.get(heap.size() - 1));
            heap.remove(heap.size()-1);
            
            int pos = 1;
            while((pos * 2) < heap.size()) {
                
                int min = heap.get(pos * 2);
                int minPos = pos * 2;
                
                if (((pos*2 + 1) < heap.size()) && min > heap.get(pos*2 + 1)) {
                    min = heap.get(pos*2 + 1);
                    minPos = pos * 2 + 1;
                }
                
                if(heap.get(pos) < min)
                    break;
                
                // 부모 자식 노드 교환
                int tmp = heap.get(pos);
                heap.set(pos, heap.get(minPos));
                heap.set(minPos, tmp);
                pos = minPos;
            }
            
            return deleteItem;
        }
    }
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        minHeap heap = new minHeap();
        
        for (int i = 0; i < N; i++) {
            int val = Integer.parseInt(br.readLine());
            
            if(val == 0) {
                System.out.println(heap.delete());
            } else {
                heap.insert(val);
            }
        }
        
    }
 
}

 

 

 

 

최대힙(MaxHeap) 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
 
public class MaxHeap {
    
    public static class maxHeap {
        
        private ArrayList<Integer> heap;
        
        public maxHeap() {
            heap = new ArrayList<>();
            heap.add(1000000); // 인덱스 1부터 시작하기 위함
        }
        
        public void insert(int val) {
            heap.add(val);
            int p = heap.size() - 1;
            // 루트까지 이동, 자식노드가 더 크면 swap
            while(p > 1 && heap.get(p / 2) < heap.get(p)) {
                int temp = heap.get(p / 2);
                heap.set(p/2, heap.get(p));
                heap.set(p, temp);
                
                p = p / 2;
            }
        }
        
        public int delete() {
            
            if(heap.size()-1 < 1) {
                return 0;
            }
            
            int deleteItem = heap.get(1);
            
            heap.set(1, heap.get(heap.size()-1));
            heap.remove(heap.size()-1);
            
            int pos = 1;
            while((pos*2) < heap.size()) {
                
                int max = heap.get(pos*2);
                int maxPos = pos * 2;
                
                if(((pos*2+1) < heap.size()) && max < heap.get(pos*2+1)) {
                    max = heap.get(pos*2+1);
                    maxPos = pos*2+1;
                }
                
                if(heap.get(pos) > max) {
                    break;
                }
                
                int temp = heap.get(pos);
                heap.set(pos, heap.get(maxPos));
                heap.set(maxPos, temp);
                pos = maxPos;
            }
            
            return deleteItem;
        }
        
        
    }
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        maxHeap heap = new maxHeap();
        
        for (int i = 0; i < N; i++) {
            int val = Integer.parseInt(br.readLine());
            
            if(val == 0) {
                System.out.println(heap.delete());
            } else {
                heap.insert(val);
            }
        }
    }
 
}

 

최대 힙을 구현할 때는 0번째 인덱스에 큰 값을 넣어서 insert 단계에서 0번째 인덱스와 swap되지 않도록 만들었다.

 

 

최소 힙과 최대 힙을 구현하는 백준 문제는 아래와 같다.

 

최소 힙 문제

1927번: 최소 힙

최대 힙 문제

11279번: 최대 힙

 

우선순위 큐 라이브러리를 가져와서 사용하면 빨리 풀 수 있지만, 직접 힙을 구현해서 풀어 익숙해지자!