[자료구조] Java - Heap(힙) 이론정리 + 구현 + Priority Queue(우선순위 큐)

자료구조 힙(Heap) 이란?

• 완전 이진 트리(마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있는 트리의 형태)의 일종으로 우선순위 큐(Priority Queue)를 위하여 만들어진 자료구조
• 여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.
• 힙은 형제노드 간의 우선순위를 고려하지 않고 부모 노드와 자식 노드의 키 값만 고려한다. 이러한 정렬 상태를 반정렬 상태 혹은 느슨한 정렬 상태 또는 약한 힙이라고 불린다.
• 힙 트리에서는 중복된 값을 허용한다.

---

Heap의 종류

• 최대 힙(max heap)
  • 부모 노드의 키값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  • key(부모 노드) >= key(자식 노드)
• 최소 힙(min heap)
  • 부모 노드의 키 값이 자삭 노드의 키 값보다 작거나 같은 완전 이진 트리
  • key(부모 노드) <= key(자식 노드)

 

출처:&nbsp;https://go-coding.tistory.com/25

---

Heap의 구현

• 힙을 저장하는 표준적인 자료구조는 배열이다.
• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않는다. = 시작 인덱스(root)는 1부터 시작한다.
• 특정 위치의 노드 번호(인덱스)는 새로운 노드가 추가되어도 변하지 않는다.(불변)
  • 예를 들어 루트 노드의 오른쪽 노드의 번호는 항상 3이다.
• 배열 힙의 성질
  1. 왼쪽 자식 노드 인덱스 = 부모 노드의 인덱스 * 2
  2. 오른쪽 자식의 노드 인덱스 = 부모 노드의 인덱스 * 2 + 1
  3. 부모 노드의 인덱스 = 자식 노드 인덱스 / 2

출처:&nbsp;https://velog.io/@sunil1369/자바-Heap-구현해보기

 

---

Heap의 삽입 연산

- 시간복잡도: O(logN)

1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입힌다.
2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킨다.

 

 

 

heap = [0,2,3,5,4,7,6] 에 1 삽입하기

1. 제일 마지막 단말 노드에 데이터를 삽입한다.
   
2. 부모 노드랑 계속 비교하면서 부모 노드가 자신보다 크다면 부모와 자신의 위치를 swap

1. 2번 조건을 만족하지 않을 때까지 또는 자신이 루트 노드가 아닐 때까지 반복한다.

 

 

Min Heap 삽입 구현

class MinHeap {
    private ArrayList<Integer> heap;

    /*heap init*/
    public MinHeap(){
    	// heap 의 인덱스는 알기 쉽게 0부터 시작한다는 특성을 따른다(0번째 인덱스 값 0)
        heap = new ArrayList<>(Arrays.asList(0,2,3,5,4,7,6)); 
    }

    // insertion
    private void insert(int data) {
        heap.add(data);
        int position = heap.size() - 1;
        // 루트 노드까지 이동했거나, 부모 Heap이 자식 Heap보다 작을 때 까지
        while(position > 1 && heap.get(position) < heap.get(position / 2)) {

            /*부모 노드와 자식 노드간의 swap을 위한 연산*/
            int temp = heap.get(position / 2);
            heap.set(position / 2, heap.get(position));
            heap.set(position, temp);

            position /= 2;
        }
    }
}

 

---

Heap의 삭제 연산

- 시간복잡도: O(logN)

 

최소 힙의 삭제 연산은 루트 노드를 삭제하는 것이다. => 최대힙도 마찬가지

 

루트 노드를 삭제하면 삽입 연산과 마찬가지로 특정을 만족시켜주는 연산이 일어나는데, 다시 한 번 말 하지만 부모 노드의 값이 자식 노드의 값보다 작아야 하는 특성을 만족 시켜야 하는 것이다.

 

이 때 사용하는 개념이 다음에 배울 우선순위 큐인데, 미리 맛을 본다 생각하고 과정을 봐보자.

1. 루트 노드 삭제
2. 말단 노드 루트 노드로 변경
3. 자식 값과 비교하여 Heap의 특성을 만족시킨다.
4. 특성을 만족할 때 까지 위와 같은 과정을 반복한다.

 

 

heap = [0, 1, 3, 2, 4, 7, 6, 5] 에서 최소값 삭제하기(min heap 삭제)

1. 가져올 '최소값'을 미리 저장해준다.

출처: https://velog.io/@jaenny/자료구조-힙-최소힙-최대힙

 

2. 가장 마지막 노드의 값과 루트 노드의 값을 Swap 해준다.
1과 5의 위치가 바뀌었다.
가장 마지막 노드와 루트 노드의 값을 바꿔주는 이유는 완전 이진 트리를 상태를 유지하기 위해서 이다. Swap이 끝났다면 말단노드(지금은 최소값)는 할 일이 끝났기 때문에 pop 시켜줘도 된다!

https://velog.io/@jaenny/자료구조-힙-최소힙-최대힙

 

 

3.현재 노드에서 자식 노드와 비교 하면서 자식 노드가 더 작은 값이라면 Swap해준다.
자식 노드는 두 개가 있다. 여기서 어떤 자식 노드를 선택해야 할까?
지금은 최소 힙을 구현하는 과정이기 때문에, 두 자식 노드 중 더 작은 값을 가지는 노드를 위로 올리면 된다.

https://velog.io/@jaenny/자료구조-힙-최소힙-최대힙

 

4. 위치를 찾을 때 까지 3번 과정을 반복한다.

 

 

 

Min Heap 삭제 구현

// delete
private 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;
    }

 

 

---

전체 코드

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;

public class HeapEx {
    static class MinHeap {
        private ArrayList<Integer> heap;

        /*heap init*/
        public MinHeap(){
            // 초기 heap 생성
            heap = new ArrayList<>(Arrays.asList(0,2,3,5,4,7,6));
        }

        // insertion
        private void insert(int data) {
            heap.add(data);
            int position = heap.size() - 1;
            // 루트 노드까지 이동했거나, 부모 Heap이 자식 Heap보다 작을 때 까지
            while(position > 1 && heap.get(position) < heap.get(position / 2)) {

                /*부모 노드와 자식 노드간의 swap을 위한 연산*/
                int temp = heap.get(position / 2);
                heap.set(position / 2, heap.get(position));
                heap.set(position, temp);

                position /= 2;
            }
            System.out.println("min heap 삽입 후 heap: " + heap);
        }

        // delete
        private ArrayList delete() {
            // heap 사이즈가 1보다 작으면 즉, 힙에 값이 없으면 return 0;
            if(heap.size() - 1 < 1) {
                return null;
            }

            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 heap;
        }
    }

    public static void main(String[] args) throws IOException {
        MinHeap mh = new MinHeap();

        mh.insert(1);
        System.out.println("min heap 삭제 후 heap: " + mh.delete());
    }
}

 

다음으로는 우선순위 큐에 대해 간략히 알아보겠다.

둘을 같이 묶어서 정리한 이유는 우선순위 큐가 힙 자료구조로 구현할 수 있기 때문이다.

---

우선순위 큐(Priority Queue)란?

큐(Queue)는 먼저 들어오는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다.

우선순위 큐(Priority Queue)는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.

 

우선순위 큐는 일반적으로 힙(Heap)을 이용하여 구현한다.

 

 

📗참고사이트

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

 

자바 - Heap 구현해보기

 

[자료 구조] 힙 자료구조와 최소 힙의 삽입, 삭제 연산 구현::

 

[자료구조 힙] 최소힙, 최대힙

 

[자료구조] 우선순위 큐와 힙 (Priority Queue & Heap)