[Data Structure 기초] Heap

 

Heap (힙)

- 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리

- 반 정렬 상태이며 중복 값이 허용된다.

 

트리구조 예시 01

트리구조 예시 02

 

Heap 시간복잡도

O(logn)

 

import java.util.PriorityQueue;

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

        // 요소 추가
        minHeap.offer(5);
        minHeap.offer(2);
        minHeap.offer(8);
        minHeap.offer(1);

        // 최소값 확인
        int minValue = minHeap.peek();
        System.out.println("Min value: " + minValue); // Min value: 1

        // 최소값 삭제
        int deletedValue = minHeap.poll();
        System.out.println("Deleted value: " + deletedValue); // Deleted value: 1

        // 최소값 확인
        minValue = minHeap.peek();
        System.out.println("Min value: " + minValue); // Min value: 2
    }
}

 

장점

- 힙 정렬은 정렬을 위해 추가적인 메모리(즉, 인플레이스 정렬)를 필요로 하지 않아 메모리 효율이 좋다.
- 동일한 값을 가진 레코드의 상대적인 순서가 정렬 후에 변경될 수 있다.

단점

- 힙 정렬은 연속된 메모리 위치에 접근하지 않기 때문에 현대의 컴퓨터 아키텍처에서 캐시 효율성이 떨어짐.
- 동일한 값의 원소 간의 상대적 순서가 중요한 경우에는 다른 정렬 알고리즘을 고려해야 함
- 힙 구조를 만들고 유지하는 데 필요한 연산이 복잡함

 

 

 

 

관련link

https://hoehen-flug.tistory.com/32

[자료구조] 힙(Heap) 자료구조 알아보기 & Java 예제 코드

https://velog.io/@suk13574/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0Java-%ED%9E%99heap

[자료구조/Java] 힙(heap)

https://go-coding.tistory.com/25

[자료구조] 힙 개념과 JAVA로 구현

https://hyunseo-fullstackdiary.tistory.com/16

JAVA-자료구조 (Heap)

https://velog.io/@jeongbeom4693/Java-Heap-Sort

[Java] 힙 정렬(Heap Sort)

https://needactionblog.com/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-java%EB%A1%9C-%EB%B0%B0%EC%9A%B0%EB%8A%94-%ED%9E%99-%EC%A0%95%EB%A0%ACheap-sort%EC%9D%98-%EC%9B%90%EB%A6%AC%EB%B6%80%ED%84%B0-%EC%8B%A4%EC%A0%9C-%EA%B5%AC/#4_%ED%9E%99_%EC%A0%95%EB%A0%AC%EC%9D%98_%EC%9E%A5%EB%8B%A8%EC%A0%90