[자료구조] - 힙(heap)

💡힙(heap)
-힙은 완전이진트리(complete binary tree) 기반 자료구조이며,
최댓값 혹은 최솟값을 빠르게 찾을수 있게 고안된 완전 이진 트리 이다.
-부모 자식간의 관계만 중요하며 형제 노드들과는 관계가 없다.
-우선 순위 큐에 사용되며 트리로 작성된다.

-삽입(Insertion) : Heap에 새로운 요소를 추가한다. 일반적으로 우선순위 큐에서는 우선순위에 따라 요소가 삽입된다.

-삭제(Deletion) : Heap에서 가장 우선순위가 높은 요소를 삭제한다. 최대 힙에서는 가장 큰 요소가 삭제되고, 최소 힙에서는 가장 작은 요소가 삭제된다.

💡max heap
내림차순 정렬
루트 노드가 모든 자식에 존재하는 키 중에서 가장 크다. (최댓값이 맨 위)
모든 부모 노드가 자식 노드보다 크거나 같은 값을 가져야 한다.

💡min heap
오름차순 정렬
루트 노드가 모든 자식에 존재하는 키 중에서 가장 작다. (최솟값이 맨 위)
모든 부모 노드가 자식 노드보다 작거나 같은 값을 가져야 한다.

💡예시코드

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // Integer를 저장하는 최소 힙 생성
        PriorityQueue<Integer> numberHeap = new PriorityQueue<>();

        // 요소 추가 
        numberHeap.add(5);
        numberHeap.add(2);
        numberHeap.add(8);
        numberHeap.add(1);
        
        // 최소값 확인
        int minNumber = numberHeap.peek();
        System.out.println("최소값 : " + minNumber); 

        // 최소값 삭제
        int removedNumber = numberHeap.poll();
        System.out.println("최소값 삭제 : " + removedNumber);

        // 최소값 확인
        minNumber = numberHeap.peek();
        System.out.println("최소값 : " + minNumber); 

        // 남아있는 요소 출력
        System.out.println("현재 요소 :");
        while (!numberHeap.isEmpty()) {
            System.out.println(numberHeap.poll());
        }
    }
}

-출력

최소값: 1
최소값 삭제 : 1
최소값 : 2
현재 요소 :
2
5
8