자료구조 다시보기- heap

오늘의 TIL 트리 정리하는 김에 heap 도 같이 정리

참고-엔지니어 대한민국님 유투브

heap

최대값이나 최소값을 빠르게 찾아내기 위한 완전 이진트리 기반 자료 구조.
완전 이진 트리 : 모든 노드가 왼쪽부터 차 있는 이진트리

최소 heap

작은 값을 위에 오게 해서 루트에 가장 작은 값 있음

최대 heap

큰 값을 위에 오게함

최소 heap 에 노드 삽입하기

• 완전 이진트리 만족시키기 위해 가장 아래 노드 왼쪽부터 채운다.
• 부모 노드랑 값을 비교해서 부모가 자기 자신보다 작을때까지 진행한다.

최소 heap에 노드 가져오기

• 맨 위 노드 가져옴 (최소 노드 찾기 쉽게하려고 쓰는 거니까)
• 빈 자리에 가장 아래 노드로 메꾼다.
• 자식 노드들 과 비교하면서 아래로 감

java api 로 사용하기

java.util.PriorityQueue 통해 사용할 수 있다.

기본적으로는 minHeap 을 지원해서 아래와 같이 사용 한다.

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(2);
minHeap.add(3);
minHeap.add(1);
minHeap.add(4);

System.out.println(minHeap.poll());
System.out.println(minHeap.poll());
System.out.println(minHeap.poll());
System.out.println(minHeap.poll());
System.out.println(minHeap.poll());

//출력 결과: 1 2 3 4 5 

MaxHeap 은 이를 반대로 정렬해주면 되는데, PriortyQueue 생성자 중 Comparator 를 인자로 받는게 있다.

public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

comparator – the comparator that will be used to order this priority queue. If null, the natural ordering of the elements will be used.
Throws:

여기에 comparator 로 역으로 정렬하도록 하면 된다.

여기서 역 정렬 comparator 정리해보자면

방법 1

Collections.reverseOrder() 

방법 2

Comparator<Integer> comp = ((a,b)->b.compareTo(a));

방법 1 로 하는게 편하다.

//maxheap 예시
 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
 maxHeap.add(5);
 maxHeap.add(2);
 maxHeap.add(3);
 maxHeap.add(1);
 maxHeap.add(4);
 System.out.println(maxHeap.poll());
 System.out.println(maxHeap.poll());
 System.out.println(maxHeap.poll());
 System.out.println(maxHeap.poll());
 System.out.println(maxHeap.poll());
 //출력 : 5 4 3 2 1

---