[자료구조] 힙(heap) 구조 (max heap/min heap)

heap 이란?

 

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)이다. 우선순위 큐를 구현할 때 주로 사용한다.

 

 - 부모보다 작은 값을 가진 힙을 최대힙이라 부른다.

 - 부모보다 큰 값을 가진 힙을 최소힙이라 부른다.

 - 항상 부모에 어떤 값이 오느냐에 따라 최소/최대가 달라진다.

 -키값의 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며, 특히 형제 사이에는 대소 관계가 정해지지 않는다.

 

힙은 다른 이진트리와 마찬 가지로 부모는 node/2의 인덱스에 있으며 자식은 node * 2  |  node * 2 +1에 위치해있다.

값 입력은 항상 맨 뒤에 되며 입력된 값이 부모노드와 값이 크거나 작으면 값을 바꿔주는 형태로 입력된다.

값 삭제는 항상 맨 앞에서 되며 삭제가 되면 맨 뒤에 값을 맨 앞으로 가져와 그 값이 알맞은 자리를 찾아갈 때까지 반복문을 진행한다.  

 

[코드]

 

[min heap]

import java.util.ArrayList;
 
public class MinHeap {
    private ArrayList<Integer> heap;
    
    public MinHeap() {                        //힙 생성자
        heap = new ArrayList<>();
        heap.add(0);                        //1부터 시작하기 위함.
    }
    
    public void insert(int val) {            //minHeap의 요소 추가.
        heap.add(val);
        int p  = heap.size() - 1;
        
        //힙 사이즈-1 이, 즉 마지막 인덱스값이 1보다 작아질 때 까지 진행 -> root로 이동
        while(p > 1 && heap.get(p / 2) > heap.get(p)) {   //부모 요소가 크면 계속 진행.
            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);
        
        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);                //일단 왼쪽 자식 노드가 min 값
            int minpos = pos * 2;
            
            if(((pos*2 +1)< heap.size()) && min > heap.get(pos*2+1)) {    //min값보다 오른쪽 노드가 더 작다면
                min = heap.get(pos*2 +1);                                //
                minpos = pos * 2 + 1;
            }
            
            if(heap.get(pos) < min)
                break;
            
            int temp = heap.get(pos);
            heap.set(pos, heap.get(minpos));
            heap.set(minpos, temp);
            pos = minpos;
        }
        return deleteItem;
    }
    
}
 

[max heap]

import java.util.ArrayList;
 
public class MaxHeap {
    
    ArrayList<Integer> heap;
    
    public MaxHeap() {
        heap = new ArrayList<>();
        heap.add(1000000);
    }
    
    public void insert(int val) {
        heap.add(val);
        int p = heap.size() - 1;
        
        while(p > 1 && heap.get(p) > heap.get(p / 2)) {
            int tmp = heap.get(p/2);
            heap.set(p/2, heap.get(p));
            heap.set(p, tmp);
            p = p / 2;
        }
    }
    public int delete() {
        int pos = 1;
        if(heap.size()-1 < 1) {
            return 0;
        }
        int deleteItem = heap.get(1);
        int tmp = heap.size()-1;
        heap.set(pos, heap.get(tmp));
        heap.remove(tmp);
        
        while((pos * 2) < heap.size()) {
            int max = heap.get(pos * 2);
            int maxPos = pos * 2;
            
            if((pos * 2 + 1) < heap.size() && max < heap.get(max * 2 + 1 )) {
                max = heap.get(max * 2 + 1);
                maxPos = pos * 2 + 1;
            }
            
            if(heap.get(pos) > max) {
                break;
            }
            
            int temp = max;
            heap.set(maxPos, heap.get(pos));
            heap.set(pos, temp);
            pos = maxPos;
            
        }
        
        return deleteItem;
        
        
    }
    
}