[자료구조] Heap

Heap 자료구조는  완전이진트리 구조로 최고  depth-1까지의 이진트리가 꽉 채워진 이진트리형태이다. Min heap과 Max heap으로 구현할 수 있으며, 중복값을 허용하고, 반 정렬상태(형제 node끼리는 정렬 순서를 보장하지 않음)이다. 최소값/최대값을 빠르게 찾아내는 유용한 자료구조이다.

 

 

데이터 삽입

 1. 트리의 가장 끝 위치에 데이터를 삽입

 2. 부모 노드의 키와 비교한 후 부모 자리와 교체(반복)

 

데이터 삭제

 1. root 노드를 반환 및 삭제

 2. 가장 마지막 위치의 node를 root로 변경

 3. 자식 노드 중 비교하여 부모 노드와 자리 교체(반복)

 

Java 내에서 minheap와 maxheap의 구현은 PriorityQueue : java.util.PriorityQueue 로 쉽게 할 수 있다.

 

PriorityQueue<Integer> minHeap = new PriorityQueue<>(); 

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());


PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
        return - Integer.compare(o1, o2);
    }
});

 

시간 복잡도 : 

add,remove : O(log(n))