Heap 학습

Heap 자료구조

 

최댓값, 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기반으로 한 자료구조입니다.

힙에는 두 가지 종류 최대 힙, 최소 힙이 있습니다.

이름에서도 유추할 수 있듯이 최대 힙은 가장 높은 값을 찾는 것이 목표입니다. 그리고  부모노드의 키값이 자식노드의 키값보다 항상 크며

최소 힙은 가장 낮은 값을 찾는 것이 목표이며 최대 힙의 반대로 부모노드의 키값이 자식노드의 키값보다 항상 작다는 것이 특징입니다.

두 개의 방식의 공통점은 같은 레벨의 노드의 키값끼리는 대소관계가 없다는 것입니다. (weak heap)

각 노드의 자식노드의 개수는 힙이 보편적으로 완전이진트리를 사용하므로 최대 2개를 사용합니다. 

 

삽입과 삭제의 시간복잡도는 heapify과정이 존재하기 때문에 O(logN)을 가집니다.

 

 

 

아래에는 최대힙으로 간단하게 구현하였습니다.

 

 

public class MaxHeap {

    private ArrayList<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList();
        // 실제 요소는 index 1부터 시작합니다.
        // 정렬조건에 따라 0번 index의 값이 달라집니다.
        heap.add(Integer.MAX_VALUE);
    }

    /**
     * 힙 요소 출력
     *
     */
    public void print() {
        for(int i = 1; i < heap.size(); i++) {
            System.out.print(heap.get(i) + " ");
        }
        System.out.println();
    }


    public void insert(int val) {
        // heap 마지막 삽입
        heap.add(val);
        int current = heap.size() - 1;

        // 현재 위치가 최소 level 2이며 부모 노드보다 값이 크다면 진입
        while(current > 1 && heap.get(current) > heap.get(current / 2)) {

            // 부모, 자식노드 스왑
            int temp = heap.get(current);
            heap.set(current, heap.get(current / 2));
            heap.set(current / 2, temp);

            // 현재 위치 = 부모 위치
            current = current / 2 ;
        }
        print();
    }

    public int delete() {
        // 1번부터 시작하므로 실질적으로 size 0
        if(heap.size() == 1) {
            return -1;
        }
        
        int parent = 1;

        // 루트, 마지막 노드 스왑
        int delete = heap.get(parent);
        heap.set(parent, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        // 자식노드의 위치가 size범주의 안이면 진입
        while (parent * 2 < heap.size()) {
            // 자식노드를 좌측 자식노드로 설정
            int child = parent * 2;
            
            // 자식 노드 = 좌측 자식 vs 우측 자식
            if(child + 1 < heap.size() && heap.get(child) < heap.get(child + 1)) {
                child = parent * 2 + 1;
            }
            // 자식노드 보다 자신이 더 크면 탈출
            if(heap.get(parent) > heap.get(child)) {
                break;
            }
            
            // 부모, 자식노드 스왑
            int tmp = heap.get(child);
            heap.set(child, heap.get(parent));
            heap.set(parent, tmp);
            parent = child;
        }
        print();
        return delete;
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap();
        maxHeap.insert(100);
        maxHeap.insert(10);

        maxHeap.insert(88);
        maxHeap.delete();
        maxHeap.insert(1000);
        maxHeap.insert(500);
        maxHeap.insert(30);
        maxHeap.delete();
        maxHeap.insert(0);
        maxHeap.insert(0);
    }
}