<aside> ❓ 힙(Heap)이란, 특정한 순서에 따라 정렬된 요소들을 저장하는 트리 기반의 자료구조이다.
</aside>
→ 일반적으로 **이진 힙(binary heap)**으로 구현되며, **우선순위 큐(priority queue)**와 같은 다른 추상 자료형의 구현에 주로 사용된다.
특징
- 완전 이진 트리(Complete Binary Tree) : Heap은 완전 이진 트리의 형태를 가진다.
- 부모-자식 노드 관계 : Heap의 부모 노드는 항상 자식 노드보다 우선순위가 높거나 같은 값을 가진다.
- max heap : 부모 노드가 항상 자식 노드보다 큰 값
- min heap : 부모 노드가 항상 자식 노드보다 작은 값
- 힙 속성 : Heap의 모든 부모-자식 쌍에 대해 특정한 조건을 만족해야 한다.
- max heap : 모든 부모 노드가 자식 노드보다 크거나 같은 값을 가져야 한다.
- min heap : 모든 부모 노드가 자식 노드보다 작거나 같은 값을 가져야 한다.
<aside> 💡 Heap은 우선순위 기반 작업 처리에 유리하다.
Java에서는 PriorityQueue 우선순위 큐 클래스를 사용해 Heap을 구현할 수 있다.
→ 요소 삽입 시, Heap의 속성을 유지
peek() : 최소값 or 최대값 접근poll() : 최소값 or 최대값 삭제offer() : 요소를 추가/* min heap */
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
/* max heap */
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(**Collections.reverseOrder()**);
<aside> 💡 만약 특정 기준으로 정렬하고 싶거나 큐에 저장된 객체의 어떤 속성으로 정렬하고 싶다면?
→ 클래스를 Comparable을 구현하도록 하거나 매개변수로 Comparator 전달
</aside>
프로그래머스에 있는 힙 문제들