[자료 구조] 힙 자료구조와 최소 힙의 삽입, 삭제 연산 구현:: (Heap Data Structure & Min Heap's Insertion, Delete implementation by java)

오늘 배워볼 것은 우선순위 큐를 위해 만들어진 유명한 자료구조, 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;
    }