[자료구조] 힙(Heap)이란 ?

힙(Heap)이란 ?

• 완전이진트리의 일종
• 완전이진트리와는 다르게 중복값을 허용한다.
• 최댓값이나 최솟값을 빠르게 찾아내기 위해 만들어진 자료구조

힙(Heap)의 종류

• 최대힙 : 루트의 값이 가장 큰 힙
• 최소힙 : 루트의 값이 가장 작은 힙

 

힙(Heap)의 사용사례

• 우선순위 큐

힙(Heap)의 구현

• 구현에는 보통 배열을 이용한다. 일반적으로 편하게 사용하기 위해서 0번째 인덱스는 비워둔다.
• 왼쪽자식의 인덱스 : 부모의 인덱스*2
• 오른쪽자식의 인덱스 : (부모의 인덱스*2) +1
• 부모의 인덱스 : 자식의 인덱스/2

public class MaxHeap  {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(reader.readLine());
        Heap heap = new Heap();
        for(int i=0; i<n; i++) {
            int k = Integer.parseInt(reader.readLine());
            if(k==0) {
                if(heap.size == 0) {
                } else {
                    heap.pop();
                }
            } else {
                heap.push(k);
            }
        }
    }
}
class Heap{
    int[] heap = new int[10000];
    int size = 0;

    public void swap(int x,int y){
        int temp = heap[x];
        heap[x] = heap[y];
        heap[y] = temp;
    }
    public void push(int data){
        heap[++size] = data;
        for(int i=size;i>1;i = i/2){
            int parent = i/2;
            if(heap[i]>heap[parent]){
                swap(i,parent);
            }else{
                break;
            }
        }

        System.out.print("");
    }

    public void pop(){
        System.out.print(heap[1] + " ");
        heap[1] = heap[size];
        heap[size--] = 0;
        for(int i=1; i*2<=size;) { //삭제 후 1에서 부터 힙으로 만들어주는 과정
            if(heap[i] > heap[i*2] && heap[i] > heap[i*2+1]) {
                break;
            }else if(heap[i*2] > heap[i*2+1]) {
                swap(i, i*2);
                i = i*2;
            } else {
                swap(i, i*2+1);
                i = i*2+1;
            }
        }
        System.out.print("");
    }
}