힙(Heap)

: 완전이진트리의 일종으로, 부모노드와 자식노드는 우선순위에 따라 정렬이 되어 있지만 형제 간의 순위는 정렬되어 있지 않은 반정렬 상태이다. 또한, 중복값이 허용된다.

 

힙의 종류

• 최소힙 : 부모 노드가 자식노드보다 작은 힙
• 최대힙 : 부모 노드가 자식노드보다 큰 힙

 

최소힙 알고리즘 코드

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

1927번: 최소 힙

 

import java.util.ArrayList;

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    
    public static class minHeap {
        
        private ArrayList<Integer> heap;
        
        public minHeap() {
            heap = new ArrayList<>();
            heap.add(0);
        }
        
        public int getRoot() {
            if(heap.size() - 1 < 1) {
                return 0;
            }
            
            return heap.get(1);
        }
        
        public void insert(int val) {
            
            heap.add(val);
            int p = heap.size() - 1;
            
            while(ptr > 1 && heap.get(ptr/2) > heap.get(ptr)) {
                // 자식노드보다 부모노드의 값이 크다면 값을 swap 
                int tmp = heap.get(ptr/2);
                heap.set(ptr/2, heap.get(ptr));
                heap.set(ptr, tmp);
                ptr = ptr/2;
            }
            
        }
        
        public void delete() {
            if(heap.size() - 1 < 1) {
                return ;
            }
            
            int item = 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 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;
                
            }
            
        }
        
    }
    
	public static void main(String[] args) throws IOException {
	    
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    
	    int N = Integer.parseInt(br.readLine());
	    
	    minHeap heap = new minHeap();
	    
	    StringBuilder sb = new StringBuilder();
	    
	    while(N --> 0) {
	        
	        int val = Integer.parseInt(br.readLine());
	        
	        if(val == 0) {
	            sb.append(heap.getRoot()).append("\n");
	            heap.delete();
	        } else {
	            heap.insert(val);
	        }
	        
	    }
	    
	    System.out.println(sb);
	    
	}
}

 

---

 

힙 참고 사이트

• [자료구조/Java] 힙(Heap) 구현 (tistory.com)