자료구조 힙(Heap) 예제 및 개념

자료구조: 힙(Heap)

1. 힙의 개념

• 힙(Heap)은 자료구조의 한 종류로, 특정 조건을 만족하는 트리 형태로 데이터를 저장하는 방법입니다.
• 완전 이진 트리(Complete Binary Tree) 형태로 구성됩니다.
• 최대값과 최소값을 빠르게 찾기 위해 사용됩니다.
• 주로 **우선순위 큐(Priority Queue)**와 같은 알고리즘에서 활용됩니다.

2. 힙의 종류

2.1 최대 힙(Max Heap)

• 루트 노드가 항상 가장 큰 값을 가집니다.
• 부모 노드는 자식 노드보다 항상 크거나 같습니다.

2.2 최소 힙(Min Heap)

• 루트 노드가 항상 가장 작은 값을 가집니다.
• 부모 노드는 자식 노드보다 항상 작거나 같습니다.

3. 힙과 이진 탐색 트리의 차이

• 힙은 최대값/최소값 검색을 위해 설계된 구조입니다.
• 이진 탐색 트리는 탐색을 위해 설계된 구조입니다.
• 힙의 조건:
  • 최대값/최소값이 루트 노드에 위치.
  • 삽입/삭제 후에도 완전 이진 트리 조건을 만족.
• 이진 탐색 트리의 조건:
  • 왼쪽 자식 노드는 부모 노드보다 작고,
  • 오른쪽 자식 노드는 부모 노드보다 큽니다.

4. 힙의 시간 복잡도

• 배열:
  • 데이터를 넣고 최대값/최소값을 찾으려면 O(n)이 걸립니다.
  • 예: [3, 5, 1, 9, 2] → 최대값 찾기 → 5개의 요소를 모두 확인 → O(5).
• 힙:
  • 최대값/최소값은 항상 루트 노드에 위치하므로 O(1)입니다.
  • 삽입/삭제 연산은 트리의 높이에 비례하여 O(logn)의 시간 복잡도를 가집니다.

5. 힙 연산

5.1 삽입

1. 새 노드 추가:
   완전 이진 트리의 구조에 따라 최하단부 왼쪽부터 채워집니다.
   
   
2. 위로 올라가며 정렬(Heapify Up):
   부모 노드와 비교하여 조건을 만족할 때까지 자리 교환(Swap)을 반복합니다.

5.2 삭제

1. 루트 노드 삭제:
   루트 노드(최대값 또는 최소값)를 제거합니다.
   
   
2. 마지막 노드를 루트로 이동:
   트리의 마지막 노드를 루트 노드 위치로 옮깁니다.
   
   
3. 아래로 내려가며 정렬(Heapify Down):
   최대값/최소값은 항상 루트 노드에 위치하므로 O(1)입니다.

6. 힙 구현 방식

• 힙은 일반적으로 배열로 구현됩니다.
• 배열 인덱스 계산:
  • 부모 노드 인덱스 = 자식 노드 인덱스//2
    • 예: 2//2=1 (부모 노드 인덱스는 1)
  • 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스×2
    • 예: 1×2=2(왼쪽 자식 인덱스는 2)
  • 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스×2+1
    • 예: 1×2+1=3 (오른쪽 자식 인덱스는 3)
    • 예: 2×2+1=5 (오른쪽 자식 인덱스는 5)

7. 결론

• 힙은 최대값/최소값 검색과 삽입/삭제 연산에서 배열보다 훨씬 효율적입니다.
• 시간 복잡도 비교:
  • 배열: O(n)
  • 힙: O(logn)
• 힙은 우선순위 큐 구현과 같은 효율적인 알고리즘에 필수적인 자료구조입니다.

8. JAVA로 보는 예제

import java.util.PriorityQueue;

public class HeapExample {
    public static void main(String[] args) {
        // PriorityQueue를 사용한 최소 힙 구현
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 힙에 데이터 삽입
        System.out.println("데이터 삽입:");
        minHeap.add(10);
        System.out.println("삽입: 10");
        minHeap.add(5);
        System.out.println("삽입: 5");
        minHeap.add(20);
        System.out.println("삽입: 20");
        minHeap.add(1);
        System.out.println("삽입: 1");

        // 힙 출력
        System.out.println("현재 힙 상태: " + minHeap);

        // 힙에서 데이터 삭제 (최소값 삭제)
        System.out.println("\n데이터 삭제:");
        System.out.println("삭제된 값: " + minHeap.poll());
        System.out.println("삭제된 값: " + minHeap.poll());

        // 힙 출력
        System.out.println("현재 힙 상태: " + minHeap);

        // 최상위 값 확인 (삭제 없이)
        System.out.println("\n최소값 확인: " + minHeap.peek());
    }
}

출력값

데이터 삽입:
삽입: 10
삽입: 5
삽입: 20
삽입: 1
현재 힙 상태: [1, 5, 20, 10]

데이터 삭제:
삭제된 값: 1
삭제된 값: 5
현재 힙 상태: [10, 20]
최소값 확인: 10

 

---

💡프레젠테이션 파일 참조

https://gamma.app/docs/Heap--beakshbp6ljhd89