[자료구조] Heap

Heap

 

• 최솟값 or 최댓값을 빠르게 찾아내는 자료구조
• 완전 이진 트리
• 중복 값 허용

 

 

1. 최소 힙 (Min Heap)

 

• 부모 노드의 key가 자식 노드의 key보다 작거나 같은 형태

 

 

 

2. 최대 힙 (Max Heap)

 

• 부모 노드의 key가 자식 노드의 key보다 크거나 같은 형태

 

 

 

 

 

 

최소 힙 구현하기

 

1. 삽입

 

• 트리의 가장 끝 위치에 데이터 삽입
• -> 부모 노드와 key와 비교한 후 작을 경우 부모 자리와 교체

 

public void insert(int data) {
    heap.add(data);

    int cur = heap.size() - 1;
    while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
        int parent = heap.get(cur / 2);
        heap.set(cur / 2, data);
        heap.set(cur, parent);

        cur /= 2;
    }

}

 

 

2. 삭제

 

• root 노드 반환 및 삭제
• -> 가장 마지막 위치의 노드를 root 노드로 위치시킴
• -> 자식 노드 중 작은 값과 비교 후 부모 노드가 더 크면 자리 교체 반복

 

public Integer delete() {
        if (heap.size() == 1) { // root 노드를 1부터 설정함
            System.out.println("empty");
            return null;
        }

        int root = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        int cur = 1;
        while (true) {
            int left = cur * 2;
            int right = cur * 2 + 1;
            int target = -1;
            if (right < heap.size()) {
                target = heap.get(left) < heap.get(right) ? left : right;
            } else if (left < heap.size()) {
                target = cur * 2;
            } else {
                break;
            }
            
            if (heap.get(cur) > heap.get(target)) {
                int parent = heap.get(cur);
                heap.set(cur, heap.get(target));
                heap.set(target, parent);
                cur = target;
            } else {
                break;
            }
            
        }

        return root;
    }

}