힙 (Heap)

han.user();·2023년 3월 20일
0

자료구조

목록 보기
10/14
post-thumbnail

힙이란?

힙(heap)은 데이터를 저장하고 관리하는 자료구조 중 하나로,
최대값이나 최소값을 빠르게 찾기 위한 목적으로 사용된다.

힙은 '부모값이 자식값보다 항상 크다'라는 조건을 만족하는 완전 이진 트리를 말한다.
완전이진트리는 트리의 한 종류이다. 완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전'이라는 말은 '부모는 자식을 왼쪽부터 추가하는 모양을 유지한다'는 뜻이고, '이진'이라는 말은 '부모가 가질 수 있는 자식의 개수는 최대 2개이다'라는 뜻이다.

자바에서는 java.util 패키지의 PriorityQueue 클래스를 사용하여 힙을 구현할 수 있다. PriorityQueue 클래스는 내부적으로 힙 구조를 사용하여 요소를 저장하며, add() 메서드를 통해 요소를 추가하고, poll() 메서드를 통해 최댓값 또는 최솟값을 반환하고 제거할 수 있다.

예를 들어, 다음은 정수형 값을 저장하는 최대 힙을 구현하는 예시 코드이다.

import java.util.Collections;
import java.util.PriorityQueue;

public class MaxValue {
    public static void main(String[] args) {
        // 방법 1
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        maxHeap.add(5);
        maxHeap.add(3);
        maxHeap.add(9);
        maxHeap.add(1);
        maxHeap.add(7);
        System.out.println(maxHeap.peek()); // 9

        // 방법 2
        int[] arr = {5, 3, 9, 1, 7};
        PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
        for (int num : arr) {
            heap.add(num);
        }
        System.out.println(heap.peek()); // 9

        // 방법 3 (일반for문 사용)
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            if (max < arr[i]) {
                max = arr[i];
            }
        }
        System.out.println(max); // 9
    }
}

이 코드에서는 PriorityQueue 클래스의 생성자에 Collections.reverseOrder()를 전달하여 최대 힙을 생성한다. add() 메서드를 사용하여 5,3,9,1,7을 순서대로 추가하고, peek()메소드를 사용하여 최대값이 무엇인지 출력한다. 만약 peek()메소드 대신에 poll() 메소드를 사용하면 최대값을 반환하고 제거까지 한다.

profile
I'm still hungry.

0개의 댓글