힙(Heap) 자료구조

힙(Heap)이란 ?

완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다.

힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경우 O(n)의 시간복잡도가 걸리는 반면,

힙을 사용하면 O(logn)의 시간복잡도가 소요되므로 시간적으로 효율적이기 때문입니다.

 

완전 이진 트리 (Complete Binary Tree)란 ?

이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리로 아래 그림과 같습니다.

만약, 왼쪽이 비어 있고 오른쪽이 채워져있다면 완전 이진 트리라고 할 수 없습니다.

 

힙의 특징

• 힙은 최대 힙과 최소 힙으로 나눠집니다.

최대 힙(max heap) : 부모 노드의 값이 자식 노드이 값보다 크거나 같은 완전 이진 트리. ( 부모 노드 >= 자식 노드 )

최소 힙(min heap) : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리. ( 부모 노드 <= 자식 노드 )

• 이진 탐색 트리와 다르게 힙은 중복된 값을 허용합니다.

최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조로 중복을 허용합니다.

 

• 구현을 쉽게 하기 위하여 배열의 첫 번째 인덱스인 0은 사용되지 않습니다.

 

부모 노드와 자식 노드의 관계

부모의 인덱스 = 자식의 인덱스 / 2
왼쪽 자식의 인덱스 = 부모의 인덱스 * 2
오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1

만약 8번 인덱스의 부모 노드의 인덱스를 알고 싶다면 8 / 2 = 4로 4번 인덱스가 부모 인덱스인 것입니다.

 

힙의 삽입 과정

힙에 새로운 노드가 들어오면, 새로운 노드를 힙의 마지막 노드에 이어 왼쪽부터 삽입합니다.

최대 힙에 새로운 노드를 삽입했을 경우를 보겠습니다.

 

1. 새로운 노드 8을 삽입.

 

2. 최대힙에서는 부모의 노드가 자식의 노드보다 커야합니다.

8의 부모 노드인 4는 8보다 작기 때문에 두 노드를 서로 교환 합니다. 

 

3. 8의 부모 노드인 7도 8보다 작기 때문에 두 노드를 서로 교환 합니다.

4. 8의 부모 노드 9는 8보다 크므로 최대 힙의 조건을 성립해 더 이상 교환이 일어나지 않습니다.

 

힙의 삭제 과정

만약 루트 노드가 삭제됬을 시에는 가장 말단(마지막)의 노드를 루트 노드자리로 대체한 후 재구조화 과정을 수행합니다.

최대 힙의 경우를 보겠습니다.

 

1. 루트 노드가 삭제 되면, 가장 말단의 노드가 루트로 이동합니다.

 

2. 루트 노드자리가 대체 된 후 재구조화 과정을 수행합니다. ( 최대 힙일 경우 예시 )

 

3.더 이상 교환할 노드가 없다면 재구조화 과정은 종료되고, 힙 구조가 완성됩니다.

 

최대 힙 구현 코드

import java.util.ArrayList;
import java.util.List;

class MaxHeap {
    private static List<Integer> heap;

    public MaxHeap() {
        heap = new ArrayList<Integer>();
        heap.add(0); //첫번째 인덱스는 사용하지 않음
    }

    //삽입
    public void insert(int num) {
        //맨 마지막 위치에 삽입
        heap.add(num);

        int newNodeIdx = heap.size() - 1; //새로 넣은 노드의 인덱스 위치 정보
        //루트까지 이동. ( 부모보다 자식이 더 크면 교환 )
        while (newNodeIdx > 1 && heap.get(newNodeIdx) > heap.get(newNodeIdx / 2)) {
            int parentNode = heap.get(newNodeIdx / 2);

            // 부모 노드와 자식 노드 교환
            heap.set(newNodeIdx / 2, heap.get(newNodeIdx));
            heap.set(newNodeIdx, parentNode);

            // 교환이 일어 났다면 자식 인덱스를 부모 인덱스로 변경.
            newNodeIdx /= 2;
        }
    }

    //삭제
    public int delete() {
        // 힙 이 비어있으면 0 리턴
        if (heap.size() - 1 < 1) {
            return 0;
        }

        // 삭제할 루트 노드 값 저장
        int deleteNode = heap.get(1);

        // 맨 마지막 자식 노드를 루트 노드와 교체한 뒤, 마지막 값 삭제
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);

        // 루트에 새로 넣은 노드의 인덱스 정보
        int newRoot = 1;

        while ((newRoot * 2) < heap.size()) {
//            int leftChild = heap.get(newRoot * 2);
//            int rightChild = heap.get(newRoot * 2 + 1);
//            int leftIdx = newRoot * 2;
//            int rightIdx = newRoot * 2 + 1;
            int leftChild = heap.get(newRoot * 2);
            int leftIdx = newRoot * 2;

            //오른쪽 자식이 존재하고 오른쪽 자식이 왼쪽 자식보다 클때 바꿀 자식 오른쪽으로 설정
            if ((newRoot * 2 + 1) < heap.size() && leftIdx < heap.get(newRoot * 2 + 1)) {
                leftChild = heap.get(newRoot * 2 + 1);
                leftIdx = newRoot * 2 + 1;
            }

            // 부모가 더 크면 끝
            if (heap.get(newRoot) > leftChild) {
                break;
            }

            //자식이 더 크면 교환
            int tmp = heap.get(newRoot);
            heap.set(newRoot, leftChild);
            heap.set(leftIdx, tmp);
            newRoot = leftIdx;
        }

        return deleteNode;
    }
}