Heap

Heap

---

Heap이란 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 하기 위해서 고안된 완전 이진 트리를 기본으로 한 자료구조이다. 완전 이진 트리란 아래 그림과 같이 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다.

 

 

Heap은 최댓값을 구하기 위한 Max Heap(최대 힙)과 최솟값을 구하기 위한 Min Heap(최소 힙)으로 분류할 수 있다. Max Heap은 부모노드의 값이 자식노드들의 값보다 항상 크거나 같고 Min Heap은 부모노드의 값이 자식노드들의 값보다 항상 작거나 같다. Binary Search Tree(이진 탐색 트리)와 Heap과의 가장 큰 차이점은 Binary Search Tree는 자료를 빠르게 탐색하기 위한 자료 구조이며 Heap은 자료들 중에서 최댓값 또는 최솟값을 빠르게 찾기 위한 자료구조라고 할 수 있다.

 

Heap의 구조

---

Heap은 대체적으로 배열로 구현된다. 완전 이진 트리를 기본으로 하고 있기 때문에 비어있는 공간이 없어 배열로 구현하기 용이하기 때문이다. 또한 자료를 삽입, 탐색하기 위해서는 아래의 세가지 인덱스 번호를 알아내는 공식을 알아야 한다.

• 부모 노드의 인덱스 번호 = 자식 노드 인덱스 번호 / 2
• 왼쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2
• 오른쪽 자식 노드의 인덱스 번호 = (부모 노드 인덱스 번호 * 2) + 1

위 그림을 예로 들면 1번 인덱스의 부모 노드의 입장에서 왼쪽 자식노드는 2번(부모 노드 인덱스 번호 * 2) 그리고 오른쪽 자식노드는 3번(부모 노드 인덱스 번호 * 2 + 1)이며, 5번 인덱스 입장에서 부모 노드는 2번(자식 노드 인덱스 번호 / 2)라고 할 수 있다.

 

Max Heap의 삽입

---

Heap은 완전 이진 트리 이므로 삽입할 노드는 기본적으로 왼쪽 최하단부터 채워지게 된다. 하지만 Max Heap의 경우 부모 노드는 항상 자식 노드의 값보다 크다는 조건을 가지고 있다. 따라서 왼쪽 최하단에 삽입만 하게 되면 Max Heap의 조건이 깨지게 된다. 그러므로 삽입을 한 후 Max Heap의 조건을 만족할 수 있게 노드들의 위치를 바꿔가며 힙을 재구조화해주어야 한다. 삽입의 재구조화는 삽입된 노드의 부모 노드와 값을 비교하여 부모 노드가 작은 값을 가지게 되면 Swap을 진행하고 크면 그 시점에서 Max Heap의 조건이 갖춰지므로 재구화가 종료 된다. 아래 그림을 보면 삽입된 20이 처음에는 왼쪽 최하단인 8의 자식 노드로 위치를 하게 되었다. 그 후 Max Heap의 조건을 갖추기 부모 노드와 비교를 통하여 재구조화가 거치게 된 것을 볼 수 있다.

 

import java.util.ArrayList;
import java.util.Collections;

public class MyHeap {
    private ArrayList<Integer> heap = new ArrayList<>();

    public MyHeap() {
        //배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함
        this.heap.add(null);
    }

    //insert를 할 시 swap 필요 여부를 확인하는 메소드
    public boolean moveUp(int insertIdx) {
        if (insertIdx <= 1) {
            //첫번째 노드까지 모두 확인이 끝났을 경우
            return false;
        } else {
            int parentInsertIdx = insertIdx / 2;

            if (this.heap.get(insertIdx) > this.heap.get(parentInsertIdx)) {
                //swap이 필요한 경우
                return true;
            } else {
                //swap이 필요 없는 경우
                return false;
            }
        }
    }

    public boolean insert(int data) {
        this.heap.add(data);

        if (this.heap.size() == 2) {
            //root 노드 insert의 경우(swap대상이 없으므로 바로 종료)
            return true;
        } else {
            int insertIdx = this.heap.size() - 1;
            while (moveUp(insertIdx)) {
                int parentInsertIdx = insertIdx / 2;
                //swap 진행
                Collections.swap(this.heap, parentInsertIdx, insertIdx);
                insertIdx = parentInsertIdx;
            }

            return true;
        }
    }
}

 

Max Heap의 삭제

---

Heap의 삭제는 최상단 노드인 root노드부터 삭제가 시작된다. root노드를 삭제 후에 왼쪽 최하단 즉 제일 마지막에 위치한 노드를 root노드로 이동을 시킨다. 삽입과 마찬가지로 해당 상태로 두게 되면 Max Heap의 조건에 어긋나게 되므로 조건을 맞추기 위해 재구조화를 거치게 된다. 삭제의 재구조화는 root노드와 root노드의 자식과의 값(자식 노드가 두개이면 두 자식노드 중 큰 값)을 비교하여 자식 노드가 크면 Swap을 진행하고 작을 시에는 그 시점에서 Max Heap의 조건이 갖춰 지므로 구조화가 종료가 된다. 아래 그림을 보면 root노드인 20을 삭제를 하였고 제일 마지막에 위치한 8을 root노드로 이동시켰다. 그 이후 자식 노드 중에 큰 값을 가지고 있는 15와 root노드의 8과 비교를 하여 자식 노드가 더 크므로 Swap이 이루어 졌다. 그 후에는 자식 노드가 없으므로 재구조화가 종료되어 Heap의 모든 조건을 갖추게 된 것을 볼 수 있다. 

//pop을 할 시 swap 필요 여부를 확인하는 메소드
    public boolean moveDown(int poppedIdx) {
        //pop을 진행하는 왼쪽 노드
        int leftPoppedIdx = poppedIdx * 2;
        //pop을 진행하는 오른쪽 노드
        int rightPoppedIdx = (poppedIdx * 2) + 1;

        if(leftPoppedIdx >= this.heap.size()) {
            // CASE1: 왼쪽 자식 노드도 없을 때 (자식 노드가 하나도 없을 때)
            return false;
        } else if(rightPoppedIdx >= this.heap.size()) {
            // CASE2: 오른쪽 자식 노드만 없을 때
            if(this.heap.get(leftPoppedIdx) > this.heap.get(poppedIdx)) {
                return true;
            } else {
                return false;
            }
        } else {
            // CASE3: 왼쪽/오른쪽 자식 노드가 모두 있을 때
            if (this.heap.get(leftPoppedIdx) > this.heap.get(rightPoppedIdx)) {
                if(this.heap.get(leftPoppedIdx) > this.heap.get(poppedIdx)) {
                    return true;
                } else {
                    return false;
                }
            } else {
                if(this.heap.get(rightPoppedIdx) > this.heap.get(poppedIdx)) {
                    return true;
                } else {
                    return false;
                }
            }
        }
    }

    public Integer pop() {
        if (this.heap.size() == 1) {
            //모든 노드가 없는 경우
            return null;
        } else {
            int returnData = this.heap.get(1);
            //root 노드에 마지막에 insert된 노드로 셋팅
            this.heap.set(1, this.heap.get(this.heap.size() - 1));
            //마지막 노드 제거
            this.heap.remove(this.heap.size() - 1);
            int poppedIdx = 1;

            while (moveDown(poppedIdx)) {
                //swap이 필요한 경우
                int leftPoppedIdx = poppedIdx * 2;
                int rightPoppedIdx = (poppedIdx * 2) + 1;

                if (rightPoppedIdx >= this.heap.size()) {
                    // CASE2: 오른쪽 자식 노드만 없을 때
                    Collections.swap(this.heap, leftPoppedIdx, poppedIdx);
                    poppedIdx = leftPoppedIdx;
                } else {
                    // CASE3: 왼쪽/오른쪽 자식 노드가 모두 있을 때
                    if (this.heap.get(leftPoppedIdx) > this.heap.get(rightPoppedIdx)) {
                        Collections.swap(this.heap, leftPoppedIdx, poppedIdx);
                        poppedIdx = leftPoppedIdx;
                    } else {
                        Collections.swap(this.heap, rightPoppedIdx, poppedIdx);
                        poppedIdx = rightPoppedIdx;
                    }
                }
            }

            return returnData;
        }
    }