힙 (heap) 개요, 자바로 구현

1. 개요

힙은 두가지 의미가 있다.

1. 완전 이진 트리인 힙, 2. 자바 메모리 영역

여기서 말하는 힙은 자료구조 힙이다.

 

힙의 특징으로는

• 트리 형태의 자료구조
• 힙의 종류에 따라 상 하의 관계만 중요하지 좌 우는 중요하지 않다.
• 최대, 최소를 기준으로 데이터를 찾는 연산이 빠르다. O(1)

상 하의 관계가 중요하단 말은 힙의 종류를 보면서 설명하는 게 편하겠다.

 

. 최대 힙(Max Heap)

부모 노드의 값은 항상 자식 노드 보다 크거나 같음

루트 노드 = 트리의 최대값

      9

    5  7

  4 2 

 

. 최소 힙(Min Heap)

부모 노드의 값은 항상 자식 노드 보다 작거나 같음

루트 노드 = 트리의 최소값

       1

     6   2

   7 8 

 

연산 속도의 경우,

• 최대/ 최소 찾기 : O(1)
• 삽입 : O(logN) (1/2 씩 줄여가니)
• 삭제 : O(logN)

응용 방법으로는

• 우선순위 큐 (Priority Queue) : 데이터가 들어온 순서에 관계없이 우선순위가 높은 데이터 순으로 처리하는 큐

등이 있다.

 

2. 구현

package heap;

public interface IHeap<T> {
    void insert(T val);

    boolean contains(T val);

    T pop();

    T peek();

    int size();
}

 

package heap;

import java.util.Arrays;
import java.util.Collections;

public class MaxHeap<T extends Comparable<T>> implements IHeap<T> {

    T[] data;
    int size;
    int maxSize;

    public MaxHeap(int maxSize) {
        this.maxSize = maxSize;
        this.data = (T[]) new Comparable[maxSize + 1];
        this.size = 0;
    }

    private int parent(int pos) {
        return pos / 2; // 부모의 위치 인덱스
    }

    private int leftChild(int pos) {
        return pos * 2;
    }

    private int rightChild(int pos) {
        return (pos * 2) + 1;
    }

    private boolean isLeaf(int pos) {
        return (pos > (size / 2) && pos <= size);
        // 인덱스 위치가 사이즈의 반 이상이면 leaf
    }

    @Override
    public void insert(T val) {
        this.data[++this.size] = val;

        int current =  this.size; // 데이터가 삽입된 위치
        while (this.data[parent(current)] != null && // 현재가 null이 아니고 부모보다 큼
                this.data[current].compareTo(this.data[parent(current)]) > 0) {
            Collections.swap(Arrays.asList(this.data), current, parent(current));
            current = parent(current); // heap의 조건 확인 (스왑된 위치로 current의 노드를 바꿔줌)
        }
    }

    @Override
    public boolean contains(T val) {
        for (int i = 1; i <= this.size; i++) {
            if (val.equals(this.data[i])) {
                return true;
            }
        }
        return false;
    }

    @Override
    public T pop() {
        T top = this.data[1];

        this.data[1] = this.data[this.size--];
        heapify(1);
        return top;
    }

    private void heapify(int idx) {
        if (isLeaf(idx)) {
            return;
        }
        T current = this.data[idx];
        T left = this.data[leftChild(idx)];
        T right = this.data[rightChild(idx)];

        if (current.compareTo(left) < 0 || // 둘 중 하나라도 자신보다 큰 지 확인
            current.compareTo(right) < 0) {
            if (left.compareTo(right) > 0) {
                // 자식 중 값이 큰 걸 넣어야 하니 어느쪽인지 확인
                Collections.swap(Arrays.asList(this.data), idx, leftChild(idx));
                heapify(leftChild(idx));
            } else {
                Collections.swap(Arrays.asList(this.data), idx, rightChild(idx));
                heapify(rightChild(idx));
            }
        }
    }

    @Override
    public T peek() {
        if (this.size < 1)
            throw new RuntimeException();
        return this.data[1];
    }

    @Override
    public int size() {
        return this.size;
    }
}

 

3. 설명

여기서 구현한 Heap은 큰 노드가 위로 가는 MaxHeap이다. 그런데 부등호만 바꿔주면 MinHeap으로 만들 수 있다.

 

3-1. 멤버 변수 (Member Variable), 생성자 (Constructor)

우선, 힙은 일차원 배열에서도 표현할 수 있다.

들어오는 데이터에 따라 변하는 제네릭 T를 담는 배열, data, 사이즈, 최대 크기 라는 멤버변수를 가진다.

 

생성자는 최대 크기가 들어오면, 최대 크기 + 1 (연산을 편하게 하기 위해 0번째는 비워둠) 크기의 배열을 생성한다.

처음엔 들어온 데이터가 없으니 사이즈는 0이다.

 

 

3-2-1. parent()

일차원 배열이니 부모, 자식 노드를 편하게 찾으려고 만들었다.

자신의 인덱스 / 2 를 하면 부모 노드의 인덱스가 나온다.

 

3-2-2. leftChild() 

자신의 인덱스 * 2를 하면 자신의 왼쪽 자식의 인덱스가 나온다.

 

3-2-3. rightChild()

왼쪽 자신에 + 1을 하면 오른쪽 자식이 나온다.

 

3-2-4. isLeaf()

인덱스가 사이즈의 1/2 이상이고, 사이즈보다 크지 않다면 leaf 노드다.

완전 이진 트리의 경우, depth(0부터 시작)가 k라고 하면, 꽉 찼을 경우, 2^(k + 1) - 1의 크기가 된다.

그러니 depth가 하나 늘어날 때마다 제곱된 수의 노드가 leaf가 되니 저걸로 leaf인지 확인할 수 있다.

 

 

3-3. insert()

힙에 데이터를 집어넣는 메소드다.

우선 1 증가시킨 사이즈의 인덱스에 데이터를 집어넣는다. 처음 0이니 첫 데이터는 1에 들어간다.

 

current는 지금 데이터의 인덱스다.

만약 지금 데이터의 부모 노드가 null이 아니고, 지금 데이터와 부모 노드의 데이터를 비교했을 때,

지금 게 크다면 while문이 돈다.
current와 parrent 위치에 있는 데이터를 바꾸고, 인덱스도 바꿔준다. MaxHeap이고 위가 커야하니 자식이

크면 계속 스왑해주면서 데이터를 삽입한다.

 

 

3-4. contains()

인수로 들어온 데이터가 힙에 있나 확인한다.

size만큼 다 뒤져보고 있으면 true, 없으면 false 반환

 

 

3-5. heapify()

힙의 규칙을 지켜주는 함수다.

인덱스가 leaf면 종료

current는 인수로 받은 데이터의 인덱스, left는 왼쪽 자식 노드의 인덱스, right는 오른쪽 자식 노드의 인덱스

 

첫 if 현재 데이터가 왼쪽 자식, 오른쪽 자식 둘 중 하나보다 작으면 돈다.

첫 if 가 충족된 상태에서 왼쪽 자식이 오른쪽 자식보다 크면, 부모와 왼쪽 자식을 스왑하고, 스왑된 위치에서

부모 노드로 다시 자식과 비교하러 간다.

 

오른쪽 노드가 크면 오른쪽 노드로 스왑하고 스왑된 위치에서 자식과 비교한다.

 

어차피 void니 return 안받아도 함수가 종료되면 끝이고, leaf에서 return되면 MaxHeap의 규칙(부모는 자식보다 크다)

을 지킨 상태에서 종료된다.

 

 

3-6. pop()

데이터를 삭제하는 메소드다.

top에 root 데이터를 넣어준다.

루트의 자리에 마지막에 들어온 노드를 넣어주고, 사이즈를 하나 줄인다. (size가 인덱스니 마지막 데이터임)

 

루트에 마지막 데이터가 들어왔는데, 이게 힙의 규칙에 맞는지 모른다. 그러니 heapify(루트) 를 돌려서 루트 자리에

있던 마지막 데이터를 적절한 위치로 보내고, 원래 노드에 있던 데이터를 반환하고 끝낸다.

 

 

3-7. peek()

데이터를 삭제하지 않고 루트의 데이터를 반환하는 함수다.

사이즈가 1보다 작다는 건 데이터가 들어오지 않았다는 말이니 에러를 일으킨다. (반환할 노드가 없음)

아니면 노드를 반환한다.

 

 

3-8. size()

힙의 사이즈를 반환한다.