힙(Heap) - 자료구조

👩‍💻 Heap 이란?

비선형 자료구조로 트리 기반의 자료구조이다. 최대 힙(Max Heap), 최소 힙(Min Heap)이 있다. 

최대 힙에서는 부모 노드가 자식 노드보다 크거나 같고, 최소 힙에서는 부모 노드가 자식 노드보다 작거나 같다.

Heap은 완전 이진 트리(Complete Binary Tree) 기반으로 만들어졌으며 이진 힙(Binary Heap)은 가장 일반적인 형태이다.

우선순위 큐를 위하여 만들어졌으므로 우선순위 큐를 구현할 때 사용되며 최대값이나 최소값을 빠르게 찾을 수 있다.

 

힙은 일종의 반 정렬 상태를 유지한다.(큰 값이 상위 레벨에 있거나 작은 값이 하위 레벨에 있다. )

또한 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.)

 

즉, 힙은 최대힙 or 최소힙을 이용하여 최대값 or 최소값을 찾는데 유리하며 아래와 같은 특징을 갖는다.

• 완전 이진 트리 형태
• 중복 값 허용
• 반 정렬 상태

* Tree에 대한 정리글 : https://sohyun119.tistory.com/32

 

✏️ 시간 복잡도

삽입 삭제 : O(logn) (매우 효율적인 편이다)

최대값 or 최소값을 찾는 시간 : O(1) (왜냐하면 루트 노드가 최대 or 최소를 가지므로)

따라서 힙은 우선순위 큐 이외에도 최대, 최소값을 찾거나 정렬할 때에 많이 사용된다. 

 

 

✏️ 힙(heap)의 종류

 

1. 최대힙 (Max heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
• key(부모 노드) >= key(자식 노드)

2. 최소힙 (Min heap)

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
• key(부모 노드) <= key(자식 노드)

 

✏️ 힙(heap)의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위해 배열의 첫 번째 index인 0은 사용되지 않는다.
• 특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.
• 힙에서의 부모노드와 자식노드 간의 관계

     - 왼쪽 자식의 index = (부모의 index) * 2

     - 오른쪽 자식의 index  = (부모의 index) * 2 + 1

     - 부모의 index = (자식의 index) / 2

 

 

 

 

✏️ 관련 문제 풀이

1. 백준 24174번 : 힙 정렬2

이번 문제는 너무 오래걸리고 어려웠다ㅜㅜ 보기에 주어진 코드랑 다르게 코드를 처음부터짰다가 테스트 코드는 맞으나... 채점결과가 계속 틀려서 차근차근 문제에 주어진 코드틀을 이용하여 다시 풀어보았다... 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class Solution{
    int count = 0;
    int k;
    int[] arr;

    public Solution(int[] arr, int k){
        this.arr = arr;
        this.k = k;
    }

    public String solution(){
        try{
            heapSort(arr);
        }catch (Exception e){
            return toString();
        }
        return "-1";
    }

    public void heapSort(int[] arr){
        int n = arr.length -1;
        buildMinHeap(arr, n);
        for(int i=n; i>=2; i--){
            swap(arr,1,i);
            heapify(arr, 1, i-1);
        }
    }
    public void buildMinHeap(int[] arr, int n){
        for(int i=n/2; i>=1; i--){
            heapify(arr, i, n);
        }
    }
    // arr[node]를 루트로 하는 트리를 최소 힙 성질을 만족하도록 수정한다.
    // arr[node]의 두 자식을 루트로 하는 서브 트리는 최소 힙 성질을 만족하고 있다.
    // n은 배열 arr의 전체 크기이며 최대 인덱스를 나타낸다.
    public void heapify(int[] arr, int node, int n){
        int smaller = 0;
        int left = 2 * node;
        int right = 2 * node + 1;
        if(right <= n){
            if(arr[left] < arr[right]){
                smaller = left;
            }else{
                smaller = right;
            }
        } else if (left <= n) {
            smaller = left;
        } else{
            return;
        }
        // 최소 힙 성질을 만족하지 못하는 경우 재귀적으로 수정
        if(arr[smaller] < arr[node]){
            swap(arr, smaller, node);
            // smaller가 루트노드가 되어 재귀함수 실행
            heapify(arr, smaller, n);
        }
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
        if(++count == k){
            throw new RuntimeException(); //
        }
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        for(int i=1; i<arr.length; i++){
            sb.append(arr[i]).append(" ");
        }
        return sb.toString();
    }

}
public class Main {
    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[n + 1];
        arr[0] = 0;
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken(" "));
        }

        System.out.println(new Solution(arr, k).solution());
    }
}

-> 노트에 정리해서 다시 공부..