즘[자료구조] 힙(Heap)

자료구조와 알고리즘/자료구조

즘[자료구조] 힙(Heap)

프린이8549 2024. 10. 7. 19:30

1. 개념

1.1. 정의

힙(Heap) 혹은 힙 트리(Heap Tree)는 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 이진트리의 자료구조를 의미한다.

영단어 힙(heap)은 "무엇인가를 차곡차곡 쌓아올린 더미"를 의미

1.2. 특징

A가 B의 부모노드일 시 A의 키값과 B의 키값 사이에 대소관계가 성립한다(형제 관계에서는 성립X)

힙은 항상 완전 이진 트리의 형태이기 때문
- 완전 이진 트리 : 트리의 위부터 아래, 오른쪽부터 왼쪽의 순서로 차있는 이진 트리
이런 성질 덕분에 최댓값 혹은 최솟값을 O(1) 안에 찾을 수 있음(루트 노드의 값)

삽입과 삭제 연산 시 힙 성질 유지 위해 힙 정렬 수행을 수행한다.

1.3. 종류

최대힙

부모 노드의 값이 자식 노드의 값보다 크거나 같음

최소힙

부모 노드의 값이 자식 노드의 값보다 작거나 같음

2. 구현

힙은 일반적으로 배열을 사용해서 구현한다.

완전 이진 트리이므로 배열의 인덱스 규칙을 활용해서 부모 및 자식 노드의 관계를 쉽게 표현할 수 있다.

다만 배열로 구현 시 계산을 편하게 하기 위해 인덱스를 1부터 사용한다.

삽입 연산

가장 끝 자리에 노드 삽입
해당 노드와 부모 노드를 서로 비교
규칙에 맞지 않을 시 부모와 교환
- 부모 노드는 (삽입된 위치의 인덱스 번호 / 2) 통해 구할 수 있음
규칙에 맞을 때까지 과정 반복(상향식 힙정렬)

삭제 연산

루트 노드 제거
루트 노드 자리에 가장 마지막 노드 삽입
- 중간에 빈 공간이 생기지 않게 하기 위함
올라간 노드와 그의 자식 노드들을 비교
조건에 맞지 않을 시 자식과 교환
- 부모모다 더 큰(작은) 자식이 하나만 있으면 해당 자식 노드와 교환
- 부모보다 더 큰(작은) 자식이 둘 있으면 자식들 중 더 큰(작은) 값과 교환
조건을 만족할 때까지 반복(하향식 힙정)

완전 이진 트리이기 때문에 해당 노드의 인덱스(i)를 알면 깊이가 얼마인지, 부모와 자식 노드가 배열의 어느 인덱스에 위치하는지 알 수 있다.

부모 노드의 위치 : i / 2
왼쪽 자식 노드의 위치 : 2 * i
오른쪽 자식 노드의 위치 : 2 * i + 1

배열을 이용한 최대힙 구현은 다음과 같다(백준 11279번)

package BOJ;

import java.io.*;

public class Main {
    /*
    BOJ NO.11279 : 최대 힙
        최대 힙 구현하기
        * 2^31 = int의 최대 범위
    */
    static int[] heap;  // 힙을 구현할 배열
    static int idx;  // 힙의 현재 위치(크기)

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 연산의 개수
        int N = Integer.parseInt(br.readLine());

        heap = new int[N + 1]; // 인덱스 1부터 시작

        idx = 0;

        StringBuilder sb = new StringBuilder();

        while(N-- > 0){
            int input = Integer.parseInt(br.readLine());
            if (input == 0){ // 0 일 경우 최댓값 출력 후 제거
                sb.append(delete()).append("\n");
            } else { // 자연수일 경우 배열에 추가
                insert(input);
            }
        }

        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }

    // 힙에 데이터 삽입
    public static void insert(int data) {
        // 1. 가장 끝 자리에 노드 삽입
        heap[++idx] = data;
        // 2. 부모 노드와 비교
        // 3. 부모 노드보다 클 때 교환
        int childNode = idx;
        int parentNode = childNode / 2;

        while (parentNode >= 1 && heap[parentNode] < heap[childNode]){
            swap(parentNode, childNode);
            childNode = parentNode;
            parentNode /= 2;
        }
    }

    // 힙에서 데이터 삭제
    public static int delete() {
        // 힙이 비어있는 경우 0 반환
        if (idx == 0) return 0;

        int maxValue = heap[1]; // 최댓값 출력 위한 변수
        // 1. 루트 노드 제거
        // 2. 루트 노드 자리에 가장 마지막 노드 삽입
        heap[1] = heap[idx--];
        // 3. 자식 노드들과 비교
        // 4. 더 큰 자식이 없을 때까지 교환
        int parentNode = 1;
        
        while(parentNode * 2 <= idx){ // 리프 노드가 아닐때까지
           int leftChild = 2 * parentNode;
           int rightChild = leftChild + 1;
           int largerChild = leftChild;
           // 자식 노드 중 더 큰 값 찾기
           if(rightChild <= idx && heap[rightChild] > heap[largerChild]){
               largerChild = rightChild;
           }
           // 자식노드보다 클 경우 탈출
           if(heap[parentNode] > heap[largerChild]) break;
            swap(parentNode, largerChild);
            parentNode = largerChild; // 더 큰 값의 노드 위치로 내려감
        }
        return maxValue;
    }
    
    // 노드 위치 교환
    public static void swap(int parentNode, int childNode){
        int temp = heap[parentNode];
        heap[parentNode] = heap[childNode];
        heap[childNode] = temp;
    }


}

3. 활용

힙은 데이터의 우선순위 기반 처리를 요구하는 다양한 시스템에서 중요한 역할을 수행한다.

3.1. 우선순위 큐

우선순위 큐의 기본 구현 자료구조로 사용된다.

3.2. 힙 정렬

정렬 알고리즘 중 하나로, 힙을 사용하여 배열을 정렬한다.

3.3. 다익스트라 알고리즘

최단 경로 탐색에서 가장 짧은 경로를 효율적으로 찾기 위해 힙이 사용된다.

3.4. 이벤트 관리

게임 및 실시간 시스템에서 이벤트 발생 순서를 관리하기 위해 힙을 사용한다.(정확하게는 우선순위 큐)

4. 참고자료

https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)