λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
πŸŽ› Others.../- 자료ꡬ쑰 & μ•Œκ³ λ¦¬μ¦˜

[자료 ꡬ쑰] νž™ μžλ£Œκ΅¬μ‘°μ™€ μ΅œμ†Œ νž™μ˜ μ‚½μž…, μ‚­μ œ μ—°μ‚° κ΅¬ν˜„:: (Heap Data Structure & Min Heap's Insertion, Delete implementation by java)

by Wonit 2020. 6. 23.

였늘 λ°°μ›Œλ³Ό 것은 μš°μ„ μˆœμœ„ 큐λ₯Ό μœ„ν•΄ λ§Œλ“€μ–΄μ§„ 유λͺ…ν•œ 자료ꡬ쑰, Heap μžλ£Œκ΅¬μ‘°μ΄λ‹€.

Heap

νž™ μžλ£Œκ΅¬μ‘°λž€? μš°μ„ μˆœμœ„ 큐λ₯Ό μœ„ν•΄ λ§Œλ“€μ–΄μ§„ 자료ꡬ쑰둜 μ΅œλŒ“κ°’κ³Ό μ΅œμ†Ÿκ°’μ„ λΉ λ₯΄κ²Œ ꡬ할 수 있으며, λ‹€μŒκ³Ό 같은 μ„Έ κ°€μ§€μ˜ νŠΉμ§•μ„ κ°–λŠ”λ‹€.

  1. μ™„μ „ 이진 트리λ₯Ό 기반으둜 κ΅¬ν˜„λœλ‹€.
  2. λŠμŠ¨ν•œ μ •λ ¬(λ°˜μ •λ ¬) μƒνƒœλ₯Ό μœ μ§€ν•œλ‹€.
  3. μ€‘λ³΅λœ 값을 ν—ˆμš©ν•œλ‹€.
  4. λ°°μ—΄λ‘œ κ°€μž₯ 효과적인 κ΅¬ν˜„μ΄ κ°€λŠ₯ν•˜λ‹€.

νž™μ˜ μ’…λ₯˜

νž™ μžλ£Œκ΅¬μ‘°λŠ” 두 κ°€μ§€μ˜ μ’…λ₯˜λ₯Ό κ°–λŠ”λ‹€.

μ΅œλŒ€ νž™

μ΅œλŒ€ νž™μ΄λž€, λΆ€λͺ¨ λ…Έλ“œμ˜ κ°’ > μžμ‹ λ…Έλ“œμ˜ 값인 νž™μ„ μ΅œλŒ€ νž™μ΄λΌκ³  ν•œλ‹€.

μ΅œμ†Œ νž™

μ΅œμ†Œ νž™μ΄λž€ μžμ‹ λ…Έλ“œμ˜ κ°’ > λΆ€λͺ¨ λ…Έλ“œμ˜ 값인 νž™μ„ μ΅œμ†Œ νž™μ΄λΌκ³  ν•œλ‹€.

νž™μ˜ ν‘œν˜„ 방법

νž™λ„ 이진 트리(Binary Tree) μ΄λ―€λ‘œ μ°¨λ‘€λŒ€λ‘œ 번호λ₯Ό λΆ€μ—¬ν•  수 있고 μ™„μ „ 이진 트리λ₯Ό 기반으둜 ν•˜κΈ° λ•Œλ¬Έμ— 각각의 λ…Έλ“œ 쀑간에 λΉ„μ–΄μžˆλŠ” λ…Έλ“œκ°€ μ—†λ‹€.

 

이 번호λ₯Ό λ°°μ—΄μ˜ 인덱슀둜 μƒκ°ν•˜λ©΄ 배열에 νž™μ˜ λ…Έλ“œλ₯Ό μ‰½κ²Œ μ €μž₯ν•˜κ³  탐색할 수 μžˆλ‹€.

 

κ·Έλž˜μ„œ νž™μ„ κ΅¬ν˜„ν•˜λŠ” κ°€μž₯ 효과적인 μžλ£Œκ΅¬μ‘°λŠ” 배열인 μ΄μœ λ„ 이 것이닀.

 

λ˜ν•œ λ§ˆμ§€λ§‰μœΌλ‘œ νŠΉμ§•μ΄ μžˆλ‹€λ©΄ 0번째 μΈλ±μŠ€λŠ” μ•Œμ•„λ³΄κΈ° μ‰½κ²Œν•˜κΈ° μœ„ν•΄μ„œ μ‚¬μš©ν•˜μ§€ μ•Šκ³  λ°”λ‘œ 1번째 인덱슀둜 μ‚¬μš©ν•œλ‹€.

 

이해λ₯Ό 돕기 μœ„ν•΄ μ‚¬μš©λœ μ΄λ―Έμ§€λŠ” λ‚΄κ°€ κ°€μž₯ μ’‹μ•„ν•˜λŠ” Heee'sλ‹˜μ˜ λΈ”λ‘œκ·Έμ— λ°œμ·Œν•œ 것이닀.

좜처 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

인덱슀 κ΅¬ν•˜κΈ°

νž™μ—λŠ” 인덱슀 λ²ˆν˜ΈλΌλŠ” νŠΉμ§•μ΄ μ‘΄μž¬ν•˜κΈ° λ•Œλ¬Έμ— λ‹€μŒκ³Ό 같은 λ°©μ‹μœΌλ‘œ 인덱슀 μœ„μΉ˜λ₯Ό ꡬ할 수 μžˆλ‹€.

  • μ™Όμͺ½ μžμ‹μ˜ 인덱슀 : (λΆ€λͺ¨μ˜ 인덱슀) * 2
  • 였λ₯Έμͺ½ μžμ‹μ˜ 인덱슀 : (λΆ€λͺ¨μ˜ 인덱슀) * 2 + 1

javaλ₯Ό μ΄μš©ν•œ heap의 κ΅¬ν˜„

MinHeap :: μ΅œμ†Œ νž™

μ΅œμ†Œ νž™μ€ μœ„μ—μ„œ 말 ν–ˆλ˜ 것 처럼 λ£¨λ“œ ν† λ“œμ— μ΅œμ†Ÿκ°’μ΄ μžˆλŠ” ν˜•νƒœμ˜ νž™μ„ λœ»ν•œλ‹€.

 

그럼 νž™μ˜ μ„±μ§ˆμ„ λ§Œμ‘±ν•˜κΈ° μœ„ν•΄μ„œλŠ” λ‹€μŒκ³Ό 같은 νŠΉμ„±μ„ κ°€μ Έμ•Όν•œλ‹€.

  1. μ™„μ „ 이진 트리의 ꡬ쑰
  2. λΆ€λͺ¨ λ…Έλ“œμ˜ 값이 μžμ‹ λ…Έλ“œμ˜ κ°’ 보닀 μž‘μ•„μ•Ό ν•œλ‹€.

μ΅œμ†Œ heap의 μ •μ˜

class MinHeap {
    private ArrayList<Integer> heap;

    /*heap init*/
    public MinHeap(){
        heap = new ArrayList<>();
        heap.add(0); // heap 의 μΈλ±μŠ€λŠ” μ•ŒκΈ° μ‰½κ²Œ 0λΆ€ν„° μ‹œμž‘ν•œλ‹€λŠ” νŠΉμ„±μ„ λ”°λ₯Έλ‹€.
    }
}

μ›λž˜λΌλ©΄ 일반 배열을 μ‚¬μš©ν•΄λ„ λ˜μ§€λ§Œ 가독성을 μœ„ν•΄μ„œ λ‚˜λŠ” ArrayList μ»¬λ ‰μ…˜μ„ μ‚¬μš©ν•˜μ˜€λ‹€.

μ΅œμ†Œ Heap의 μ‚½μž… μ—°μ‚°

일반적인 νž™μ˜ 연산을 μœ„ν•΄μ„œλŠ” λΆ€λͺ¨ λ…Έλ“œμ™€ μžμ‹ λ…Έλ“œ μ‚¬μ΄μ˜ 관계λ₯Ό μ§€μΌœμ£ΌλŠ” 연산이 ν•„μš”ν•˜λ‹€.

 

이 말이 무엇이냐면 μ•„κΉŒ μœ„μ— 말 ν–ˆλ˜ λΆ€λͺ¨ λ…Έλ“œμ˜ 값이 μžμ‹ λ…Έλ“œμ˜ 값보닀 μž‘μ•„μ•Ό ν•˜λŠ” 그런 관계λ₯Ό λœ»ν•œλ‹€.

 

μš°λ¦¬λŠ” λΆ€λͺ¨ λ…Έλ“œμ˜ 인덱슀λ₯Ό μ•Œλ©΄ μžμ‹ λ…Έλ“œμ˜ 인덱슀λ₯Ό μ•Œ 수 μžˆλ‹€.

 

그리고 μš°λ¦¬κ°€ μ§€κΈˆκΉŒμ§€ λ°°μ› λ˜ Heap의 νŠΉμ§•μ„ 적절히 μ μš©ν•˜λ©΄ μ‚½μž… 연산을 μ‰½κ²Œ μ΄μ–΄κ°ˆ 수 μžˆλ‹€.

 

과정을 ν•œ 번 λ‚˜νƒ€λ‚΄ λ³Έλ‹€λ©΄

  1. μ‚½μž…ν•  μ›μ†Œλ₯Ό Heap의 λ§ˆμ§€λ§‰ Index에 μΆ”κ°€μ‹œν‚¨λ‹€.
  2. λ§ˆμ§€λ§‰ Indexμ—μ„œ / 2λ₯Ό ν•˜μ—¬ λΆ€λͺ¨ λ…Έλ“œμ˜ 인덱슀λ₯Ό μ°ΎλŠ”λ‹€.
  3. λΆ€λͺ¨μ˜ κ°’κ³Ό λΉ„κ΅ν•˜μ—¬ Heap의 νŠΉμ„±μ„ λ§Œμ‘±μ‹œν‚¨λ‹€.
  4. μœ„μ˜ 과정을 λ°˜λ³΅ν•œλ‹€. μ’…λ£Œ 쑰건 : 루트 λ…Έλ“œκ°€ λ˜κ±°λ‚˜ λΆ€λͺ¨ λ…Έλ“œμ˜ 값이 ν˜„μž¬ λ…Έλ“œλ³΄λ‹€ μž‘μ„ λ•Œ
class MinHeap {
    private ArrayList<Integer> heap;

    /*heap init*/
    public MinHeap(){
        heap = new ArrayList<>();
        heap.add(0); // heap 의 μΈλ±μŠ€λŠ” μ•ŒκΈ° μ‰½κ²Œ 0λΆ€ν„° μ‹œμž‘ν•œλ‹€λŠ” νŠΉμ„±μ„ λ”°λ₯Έλ‹€.
    }

    // insertion
    private void insert(int data) {
        heap.add(data);
        int position = heap.size() - 1;
        // 루트 λ…Έλ“œκΉŒμ§€ μ΄λ™ν–ˆκ±°λ‚˜, λΆ€λͺ¨ Heap이 μžμ‹ Heap보닀 μž‘μ„ λ•Œ κΉŒμ§€
        while(position > 1 && heap.get(position / 2) < heap.get(position)) {

            /*λΆ€λͺ¨ λ…Έλ“œμ™€ μžμ‹ λ…Έλ“œκ°„μ˜ swap을 μœ„ν•œ μ—°μ‚°*/
            int temp = heap.get(position / 2);
            heap.set(position / 2, heap.get(position));
            heap.set(position, temp);

            position /= 2;
        }
    }
}

μ΅œμ†Œ Heap의 μ‚­μ œ μ—°μ‚°

μ΅œμ†Œ νž™μ˜ μ‚­μ œ 연산은 루트 λ…Έλ“œλ₯Ό μ‚­μ œν•˜λŠ” 것이닀.

 

루트 λ…Έλ“œλ₯Ό μ‚­μ œν•˜λ©΄ μ‚½μž… μ—°μ‚°κ³Ό λ§ˆμ°¬κ°€μ§€λ‘œ νŠΉμ •μ„ λ§Œμ‘±μ‹œμΌœμ£ΌλŠ” 연산이 μΌμ–΄λ‚˜λŠ”λ°, λ‹€μ‹œ ν•œ 번 말 ν•˜μ§€λ§Œ λΆ€λͺ¨ λ…Έλ“œμ˜ 값이 μžμ‹ λ…Έλ“œμ˜ 값보닀 μž‘μ•„μ•Ό ν•˜λŠ” νŠΉμ„±μ„ 만쑱 μ‹œμΌœμ•Ό ν•˜λŠ” 것이닀.

 

이 λ•Œ μ‚¬μš©ν•˜λŠ” κ°œλ…μ΄ λ‹€μŒμ— 배울 μš°μ„ μˆœμœ„ 큐인데, 미리 맛을 λ³Έλ‹€ μƒκ°ν•˜κ³  과정을 봐보자.

 

  1. 루트 λ…Έλ“œ μ‚­μ œ
  2. 말단 λ…Έλ“œ 루트 λ…Έλ“œλ‘œ λ³€κ²½
  3. μžμ‹ κ°’κ³Ό λΉ„κ΅ν•˜μ—¬ Heap의 νŠΉμ„±μ„ λ§Œμ‘±μ‹œν‚¨λ‹€.
  4. νŠΉμ„±μ„ λ§Œμ‘±ν•  λ–„ κΉŒμ§€ μœ„μ™€ 같은 과정을 λ°˜λ³΅ν•œλ‹€.
int delete() {
        // heap μ‚¬μ΄μ¦ˆκ°€ 1보닀 μž‘μœΌλ©΄ 즉, νž™μ— 값이 μ—†μœΌλ©΄ return 0;
        if(heap.size() - 1 < 1) {
            return 0;
        }

        int deleteData = heap.get(1); // λ£¨λ“œ λ…Έλ“œ μ‚­μ œ

        heap.set(1, heap.get(heap.size() - 1)); // 루트 λ…Έλ“œμ˜ μžλ¦¬μ— 말단 λ…Έλ“œμ˜ dataλ₯Ό μ„€μ •
        heap.remove(heap.size() - 1); // 말단 λ…Έλ“œ μ‚­μ œ

        int position = 1;
        while((position * 2) < heap.size()) { // νž™μ˜ 크기보닀 μž‘μ„ λ–„ κΉŒμ§€
            int min = heap.get(position * 2); // ν˜„μž¬ λ…Έλ“œμ˜ μ™Όμͺ½ μžμ‹ λ…Έλ“œμ˜ κ°’
            int minPos = position * 2; // ν˜„μž¬ λ…Έλ“œμ˜ μ™Όμͺ½ μžμ‹ λ…Έλ“œμ˜ 인덱슀

            // 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œμ™€ μ™Όμͺ½ μžμ‹ λ…Έλ“œ 쀑 더 큰 λ…Έλ“œμ— κ°’κ³Ό λΉ„κ΅ν•˜κ³  κ΅ν™˜ν•˜κΈ° λ•Œλ¬Έμ— μ™Όμͺ½ μžμ‹λ…Έλ“œμ™€ 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œμ˜ 값을 λΉ„κ΅ν•˜λŠ” 과정을 κ±°μΉœλ‹€.
            if(((position * 2 + 1) < heap.size()) && min > heap.get(position * 2 + 1)){  // 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œκ°€ 더 크면 λ°”κΏ”μ€˜μ•Όν•œλ‹€.
                min = heap.get(position * 2 + 1); // 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ‘œ λ³€κ²½
                minPos = position * 2 + 1; // μœ„μΉ˜ λ˜ν•œ 였λ₯Έμͺ½ μžμ‹ λ…Έλ“œλ‘œ λ³€κ²½
            }

            if(heap.get(position) < min) break; // ν˜„μž¬ λ…Έλ“œλ³΄λ‹€ μžμ‹ λ…Έλ“œμ˜ 값이 더 크면, νž™μ˜ μ„±μ§ˆμ„ λ§Œμ‘±ν•˜λ©΄ 반볡 μ’…λ£Œ

            /*μžμ‹κ³Ό λΆ€λͺ¨μ˜ SWAP κ³Όμ •*/
            int temp = heap.get(position);
            heap.set(position, heap.get(minPos));
            heap.set(minPos, temp);
            position = minPos;
        }
        return deleteData;
    }

λŒ“κΈ€