힙은 이진 트리 모양을 가지고 있는 자료구조이다.
이진 트리는 각 노드가 최대 두 개의 자식을 가질 수 있는 트리 구조를 의미한다.
힙은 최댓값, 최솟값을 빠르게 찾아내기 위해 사용되는데 우선순위 큐를 구현하는 데 활용된다.
최댓값을 찾아내는 힙을 최대힙, 최솟값을 찾아내는 힙을 최소 힙이라고 한다.
출처: https://en.wikipedia.org/wiki/Binary_heap
최소 힙에서는 부모 노드가 자식 노드보다 작아야 한다.
따라서 최상단에 있는 값이 가장 작은 값이 된다.
출처: https://en.wikipedia.org/wiki/Binary_heap
최대 힙에서는 부모 노드가 자식 노드보다 커야 한다.
우선순위 큐를 통해 최소, 최대 힙을 구현해 보겠다.
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(2);
minHeap.offer(1);
System.out.println(minHeap.poll());출력값: 1
가장 작은 값이 큐의 맨 앞에 위치해 poll()을 하면 가장 작은 값을 반환한다.
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.offer(3);
maxHeap.offer(2);
maxHeap.offer(1);
System.out.println(maxHeap.poll());출력값: 3
람다를 사용해 반대로 정렬하도록 Comperator를 구현했기 때문에 가장 큰 값이 큐의 맨 앞에 위치한다. 따라서 poll()을 하면 가장 큰 값을 반환한다.
항해99 취업 리부트 코스를 수강하고 작성한 콘텐츠 입니다.
