[자료구조] Heap 힙, 우선순위 큐

힙(Heap)

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 한 자료구조이다.

힙에는 두가지 종류가 있다.

• 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙 : 최대 힙(Max Heap)
• 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙 : 최소 힙(Min Heap)

우선 순위 큐(Priority queue)를 위해서 만들어졌다. - 힙 자체가 우선순위 큐이다.

큐는 FIFO(First In First Out, 선입선출) 자료구조인데,

우선순위큐는 들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다.

Queue의 시간 복잡도는 enqueue = O(1), dequeue O(1) 이고

Priority queue 의 시간 복잡도는 push(삽입, O(log N)), pop (삭제 O(log N)) 이다.

다만 검색은(특정 값을 찾는것) 위치에 대한 개념이 없기 떄문에 선형시간 O(n) 이다

• 자바 PriorityQueue 도 선형으로 되어있다.

시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산에 사용된다.

• 

• Tree의 형식을 취하고 있으며 Tree 중에서도 배열을 기반으로 한 (Complete Binary Tree)완전 이진 트리이다.

• 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리이다.

• 배열에 트리의 값을 넣어줄 때는 0번째는 건너뛰고 1번째부터 루트 노드가 시작된다. 이유는 노드의 고유 번호와 index를 일치시켜 혼동을 줄이기 위함이다.

• 중복된 값을 허용. (이진 탐색 트리는 중복 값을 허용하지 않음.)

• Max Heap은 루트 노드에 저장된 값이 가장 크다.

• Min Heap은 루트 노드에 저장된 값이 가장 작은값이 된다.

• 최대힙에서는 Root Node에 있는 값이 제일 크므로, 최대값을 찾는데 소요되는 연산의 시간 복잡도는 O(1)이다.

• Complete Binary Tree이기 때문에 배열을 이용해 관리할 수 있으며, 인덱스를 통한 Random Access가 가능하다.

• Index 번호는 노드 개수가 n개일 때, i번째 노드에 대하여 왼쪽 자식은 ix2, 오른쪽 자식은 ix2+1가 된다.

구현

힙을 저장하는 표준적인 자료구조는 배열이다.

구현을 쉽게 하기 위해 배열의 첫 번째 인덱스인 0은 사용되지 않고, 1부터 시작한다.
첫 번째 인덱스인 0 번을 사용하는 경우도 있는데, 그러면 부모 노드와 자식 노드의 관계 공식이 달라진다.

특정 위치의 노드 번호는 새로운 노드가 추가되어도 변하지 않는다.

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

• 왼쪽 자식 index : (부모 index) * 2
  • n번째 노드의 왼쪽 자식 = 2n
• 오른쪽 자식 index : (부모 index) * 2 + 1
  • n번째 노드의 오른쪽 자식 = 2n + 1
• 부모 index : (자식 index) / 2
  • n번째 노드의 부모 = n / 2
• 힙의 높이는l og(N) 이다.
  • push 했을 때 스왑하는 과정이 최대 logN번 반복되기 떄문에 시간복잡도는 O(log N)

삽입

• MaxHeap

  • 1. 힙에 새로운 요소가 들어오면 새로운 요소를 마지막노드에 삽입.
  • 2. bottom-up 방식으로 새 요소와 크기를 비교해가면서 새로운 요소보다 부모가 더 작으면 swap

    • int index = lastIndex(); // 마지막 인덱스. 이 기준은 루트 인덱스가 1로 가정했을때이다.
      while (부모가 존재하는가? && 그렇다면 부모가 나보다 값이 작은가?){
          swap(부모인덱스, 내 인덱스);
          index = 부모인덱스 // 스왑했으니까 부모가 되고, 다음 조건에 맞으면 새 부모와 다시 비교한다.
      }

    • heapifyUp()

• MinHeap

  • 1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 삽입.
  • 2. bottom-up 방식으로 새로운 요소와 크기를 비교해가면서 부모가 더 크면 부모와 swap

    • int childIndex = lastIndex();
      while (부모가 존재하는가? && 그렇다면 부모가 나보다 값이 큰가?) {
          swap(부모인덱스, 내 인덱스);
          childIndex = 부모인덱스 // 스왑했으니까 부모가 되고, 다음 조건에 맞으면 새 부모와 다시 비교한다.
      }

    • heapfiyUp();

• max heap일 때 들어온 값, 부모 중 부모가 작으면 부모랑 교환한다 - 부모값이 더 커야 하므로
• min heap일 때 들어올 값, 부모 중 부모가 크면 부모랑 교환한다 - 부모값이 더 작아야 하므로

힙 재구성을 heapify라고 하겠습니다.

힙을 재구성 할때는 insert와 delete시 방법이 다르다.

• insert - heapifyUp

  • 마지막 인덱스부터 루트 인덱스까지 bottom-up 방식으로 크기를 비교해서 재구성한다

• delete - heapfiyDown

  • 루트 인덱스부터 마지막 인덱스까지 top-down 방식으로 크기를 비교해서 재구성 한다.

삭제

• MaxHeap

  • 1. 힙의 루트 에서 값을 빼고, 마지막 인덱스의 값을 힙의 루트로 삽입.

  • 2. top-down 방식으로 새 루트 요소와 왼쪽 오른쪽 자식들을 비교하면서, 더 큰 값의 자식과 swap

       • int parentIndex = 1; // 인덱스를 0에서 시작하느냐, 1에서 시작하느냐에 따름. 루트 인덱스 값
         while (왼쪽 자식이 있느냐(부모인덱스)){ // 왼쪽 자식이 없으면 오른쪽 자식은 없다.
           int bigChildIndex = getLeftChildIndex(parentIndex); // 
         
           if (오른쪽 자식이 있고 && 오른쪽 자식이 왼쪽 자식보다 크다면) {
               bigChildIndex = 오른쪽 자식인덱스;
           }
         
           if (부모값이 자식값보다 크다면) {
               break;
           } else { // 부모 값이 자식보다 작다면 
               swap(부모인덱스, 더 큰 자식 인덱스);
               parentIndex = 더 큰 자식 인덱스; // 반복해가면서 비교한다
           }
         }

       • heapfiyDown();

• MinHeap

  • 1. 힙의 루트에서 값을 빼고 마지막 인덱스의 값을 힙의 루트로 삽입
  • 2. top-down 방식으로 새 루트 요소와 왼쪽, 오른쪽 자식들이 값을 비교하면서 더 작은 값의 자식과 swap

    • int parentIndex = 1; //인덱스를 0에서 시작하느냐, 1에서 시작하느냐에 따름. 루트 인덱스 값
      while (왼쪽 자식이 있느냐(부모인덱스)) {
          int smallChildIndex = getLeftChildIndex(parentIndex);
      
          if (오른쪽 자식이 있꼬 && 오른쪽 자식이 왼쪽 자식보다 더 작다면) {
              smallChildIndex = 오른쪽 자식인덱스;
          }
      
        if (부모 값이 자식보다 작다면) {
            break;
        } else { // 부모 값이 자식보다 크다면
            swap(부모 인덱스, 더 작은 자식 인덱스);
            parentIndex = 더 작은 자식인덱스;
        }
      }

    • heapifyDown();

Java Code(자바 코드) - 배열과 ArrayList를 사용한 2가지 방식.

ArrayList 사용 - 접기/펼치기

추상클래스 이용하여 구현

public abstract class ListHeap<T> {

    abstract void add(T data);

    abstract T pop();

    abstract void heapifyUp();

    abstract void heapifyDown();

    abstract T peek();

    abstract int size();

    abstract boolean contains(T data);

    abstract void swap(int i, int j);

    protected int getParentIndex(int childIndex) {
        return (int) Math.floor((int) ((childIndex - 1) / 2));// 바닥함수. 내려야한다.
    }

    protected int getLeftChildIndex(int parentIndex) {
        return (2 * parentIndex) + 1;
    }

    protected int getRightChildIndex(int parentIndex) {
        return (2 * parentIndex) + 2;
    }

    protected boolean hasRightChild(int index) {
        return getRightChildIndex(index) < size();
    }

    protected boolean hasLeftChild(int index) {
        return getLeftChildIndex(index) < size();
    }

    protected boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }

    protected int lastIndex() {
        return this.size() - 1;
    }

    public void printElements() {
        while (this.size() > 0) {
            System.out.print(this.pop() + (this.size() != 1 ? ", " : ""));
        }
    }

}

public class ArrayListMaxHeap<T extends Comparable<T>> extends ListHeap<T> {

    private final List<T> elements;

    public ArrayListMaxHeap() {
        this.elements = new ArrayList<>();
    }

    @Override
    public void swap(int i, int j) {
        final T temp = elements.get(i);
        elements.set(i, elements.get(j));
        elements.set(j, temp);
    }

    private boolean isRightChildBigThenLeftChild(int parentIndex) {
        return elements.get(getRightChildIndex(parentIndex)).compareTo(elements.get(getLeftChildIndex(parentIndex))) > 0;
    }

    private boolean isParentBiggerThenBigChild(int parentIndex, int childIndex) {
        return elements.get(parentIndex).compareTo(elements.get(childIndex)) > 0;
    }

    private boolean isParentSmallThenChild(int childIndex) {
        return elements.get(getParentIndex(childIndex)).compareTo(elements.get(childIndex)) < 0;
    }

    @Override
    public void add(T data) {
        elements.add(data);
        heapifyUp();
    }

    @Override
    protected void heapifyUp() {
        int childIndex = lastIndex();

        while (hasParent(childIndex) && isParentSmallThenChild(childIndex)) {
            swap(getParentIndex(childIndex), childIndex);
            childIndex = getParentIndex(childIndex);
        }
    }

    @Override
    public T pop() {
        if (this.size() == 0) {
            throw new ArrayIndexOutOfBoundsException("heap is empty");
        }

        final T pop = elements.get(0);

        elements.set(0, elements.get(lastIndex()));
        elements.remove(lastIndex());

        heapifyDown();

        return pop;
    }

    @Override
    protected void heapifyDown() {
        int index = 0;

        while (hasLeftChild(index)) { // 왼쪽 자식이 없으면 오른쪽 자식도 없다.
            int bigChildIndex = getLeftChildIndex(index);

            if (hasRightChild(index) && isRightChildBigThenLeftChild(index)) {
                bigChildIndex = getRightChildIndex(index);
            }

            if (isParentBiggerThenBigChild(index, bigChildIndex)) {
                break;
            } else {
                swap(bigChildIndex, index);
                index = bigChildIndex;
            }

        }
    }

    @Override
    public T peek() {
        return this.elements.get(0);
    }

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

    @Override
    boolean contains(T data) {
        return this.elements.contains(data);
    }

    public static void main(String[] args) {
        ListHeap<Integer> arrayListListHeap = new ArrayListMaxHeap<>();

        arrayListListHeap.add(5);
        arrayListListHeap.add(4);
        arrayListListHeap.add(2);
        arrayListListHeap.add(7);
        arrayListListHeap.add(8);
        arrayListListHeap.add(9);
        arrayListListHeap.add(3);
        arrayListListHeap.add(6);
        arrayListListHeap.add(15);
        arrayListListHeap.add(999);
        arrayListListHeap.add(21);
        arrayListListHeap.add(1);
        arrayListListHeap.add(2393);
        arrayListListHeap.add(8237);
        arrayListListHeap.add(9999);
        arrayListListHeap.add(999);
        arrayListListHeap.add(999);
        arrayListListHeap.add(999);


        arrayListListHeap.printElements();

    }

}

public class ArrayListMinHeap<T extends Comparable<T>> extends ListHeap<T> {

    private final List<T> elements;

    public ArrayListMinHeap() {
        this.elements = new ArrayList<>();
    }

    @Override
    public void add(T data) {
        elements.add(data);
        heapifyUp();
    }

    @Override
    public T pop() {
        if (this.size() == 0) {
            throw new ArrayIndexOutOfBoundsException("heap is empty");
        }

        final T pop = elements.get(0);

        elements.set(0, elements.get(lastIndex()));
        elements.remove(lastIndex());

        heapifyDown();

        return pop;
    }

    private boolean isParentBigThenChild(int childIndex) {
        return elements.get(getParentIndex(childIndex)).compareTo(elements.get(childIndex)) > 0;
    }

    @Override
    protected void heapifyUp() {
        int childIndex = lastIndex();

        while (hasParent(childIndex) && isParentBigThenChild(childIndex)) {
            swap(getParentIndex(childIndex), childIndex);
            childIndex = getParentIndex(childIndex);
        }
    }

    @Override
    protected void heapifyDown() {
        int index = 0;

        while (hasLeftChild(index)) { // 왼쪽 자식이 없으면 오른쪽 자식도 없다.
            int smallChildIndex = getLeftChildIndex(index);

            if (hasRightChild(index) && isRightChildSmallThenLeftChild(index)) {
                smallChildIndex = getRightChildIndex(index);
            }

            if (isParentSmallThenSmallChild(index, smallChildIndex)) {
                break;
            } else {
                swap(smallChildIndex, index);
                index = smallChildIndex;
            }
        }

    }

    private boolean isParentSmallThenSmallChild(int parentIndex, int childIndex) {
        return elements.get(parentIndex).compareTo(elements.get(childIndex)) < 0;
    }

    private boolean isRightChildSmallThenLeftChild(int parentIndex) {
        return elements.get(getRightChildIndex(parentIndex)).compareTo(elements.get(getLeftChildIndex(parentIndex))) < 0;
    }

    @Override
    public T peek() {
        return this.elements.get(0);
    }

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

    @Override
    public boolean contains(T data) {
        return this.elements.contains(data);
    }

    @Override
    protected void swap(int i, int j) {
        final T temp = elements.get(i);
        elements.set(i, elements.get(j));
        elements.set(j, temp);
    }

    public static void main(String[] args) {
        ListHeap<Integer> arrayListListHeap = new ArrayListMinHeap<>();

        arrayListListHeap.add(5);
        arrayListListHeap.add(4);
        arrayListListHeap.add(2);
        arrayListListHeap.add(7);
        arrayListListHeap.add(8);
        arrayListListHeap.add(9);
        arrayListListHeap.add(3);
        arrayListListHeap.add(6);
        arrayListListHeap.add(15);
        arrayListListHeap.add(999);
        arrayListListHeap.add(21);
        arrayListListHeap.add(1);
        arrayListListHeap.add(2393);
        arrayListListHeap.add(8237);
        arrayListListHeap.add(9999);
        arrayListListHeap.add(999);
        arrayListListHeap.add(999);
        arrayListListHeap.add(999);


        arrayListListHeap.printElements();
    }
}

배열을 이용한 힙 구현 - 접기/펼치기

public interface ArrayHeap {
    void add(int data);

    void printElements();

    boolean contains(int data);

    int peek();

    int pop();

    int size();

    default int getParentIndex(int childIndex) {
        return (int) Math.floor(childIndex / 2);// 바닥함수. 내려야한다.
    }

    default int getLeftChildIndex(int parentIndex) {
        return (2 * parentIndex) + 1;
    }

    default int getRightChildIndex(int parentIndex) {
        return (2 * parentIndex) + 2;
    }
    default boolean hasParent(int index) {
        return getParentIndex(index) >= 0;
    }

}

public class ArrayMaxHeap implements ArrayHeap {

    private int[] element;
    private int size;
    private int maxSize;

    public ArrayMaxHeap(int maxSize) {
        this.maxSize = maxSize;
        this.element = new int[maxSize + 1];
        this.size = 0;
    }

    private int leftChildValue(int parentIndex) {
        return element[getLeftChildIndex(parentIndex)];
    }

    private int rightChildValue(int parentIndex) {
        return element[getRightChildIndex(parentIndex)];
    }

    private int parentValueFromChild(int childIndex) {
        return element[getParentIndex(childIndex)];
    }

    private int parentValue(int parentIndex) {
        return element[parentIndex];
    }

    private int getParentData(int index) {
        return element[getParentIndex(index)];
    }

    private boolean isGraterThenChild(int parentIndex) {
        return parentValue(parentIndex) > leftChildValue(parentIndex) && parentValue(parentIndex) > rightChildValue(parentIndex);
    }

    private void swap(int targetIndex, int otherIndex) {
        int temp = element[targetIndex];
        element[targetIndex] = element[otherIndex];
        element[otherIndex] = temp;
    }

    @Override
    public void add(int data) {

        validateSizeAndResize();

        this.element[++size] = data;
        heapifyUpUseWhile(); // or heapifyUpUseFor();
    }

    // insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
    // maxHeap은 큰값이 부모가 되어야 한다
    private void heapifyUpUseFor() {
        for (int i = size; i > 1; i--) {
            int parentIndex = getParentIndex(i);

            if (element[parentIndex] < element[i]) {
                swap(parentIndex, i);
            }
        }
    }

    // insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
    private void heapifyUpUseWhile() {
        int childIndex = size;

        while (hasParent(childIndex) && getParentData(childIndex) < element[childIndex]) {
            swap(getParentIndex(childIndex), childIndex);
            childIndex = getParentIndex(childIndex);
        }
    }

    private void validateSizeAndResize() {
        if (size == this.maxSize) {
            element = Arrays.copyOf(element, maxSize * 2);
            maxSize *= 2;
        }
    }

    @Override
    public int pop() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("heap is empty");
        }

        int root = element[1];

        element[1] = element[size];
        element[size] = 0;
        this.size = size - 1;

        heapifyDownUseFor();// or heapifyDownUserWhile();

        return root;
    }

    // delete 할때는 루트 인덱스부터 마지막 인덱스까지 top-down 크기를 비교해서 재구성 한다.
    public void heapifyDownUseFor() {
        for (int parent = 1; parent * 2 <= size; ) {

            if (isGraterThenChild(parent)) {
                break;

            } else if (leftChildValue(parent) > rightChildValue(parent)) {
                swap(parent, getLeftChildIndex(parent));
                parent = parent * 2;
            } else {
                swap(parent, getRightChildIndex(parent));
                parent = parent * 2 + 1;
            }

        }
    }

    public void heapifyDownUserWhile() {
        int parent = 1;

        while (parent * 2 <= size) {

            if (isGraterThenChild(parent)) {
                break;

            } else if (leftChildValue(parent) > rightChildValue(parent)) {
                swap(parent, getLeftChildIndex(parent));
                parent = parent * 2;
            } else {
                swap(parent, getRightChildIndex(parent));
                parent = parent * 2 + 1;
            }

        }
    }

    @Override
    public void printElements() {
        if (this.size == 0) {
            return;
        }

        while (!(this.size == 0)) {
            System.out.print(pop() + ", ");
        }

    }

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

    @Override
    public int peek() {
        return element[1];
    }


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

    public static void main(String[] args) {
        ArrayHeap arrayMaxHeap = new ArrayMaxHeap(10);

        arrayMaxHeap.add(5);
        arrayMaxHeap.add(4);
        arrayMaxHeap.add(2);
        arrayMaxHeap.add(7);
        arrayMaxHeap.add(8);
        arrayMaxHeap.add(9);
        arrayMaxHeap.add(3);
        arrayMaxHeap.add(6);
        arrayMaxHeap.add(15);
        arrayMaxHeap.add(999);
        arrayMaxHeap.add(2134134);
        arrayMaxHeap.add(21);
        arrayMaxHeap.add(1);
        arrayMaxHeap.add(9918324);
        arrayMaxHeap.add(239328);
        arrayMaxHeap.add(8237237);
        arrayMaxHeap.add(99999999);
        arrayMaxHeap.printElements();
    }
}

public class ArrayMinHeap implements ArrayHeap {

    private int[] element;

    private int size;

    private int maxSize;

    private int leftChildValue(int parentIndex) {
        return element[getLeftChildIndex(parentIndex)];
    }

    private int rightChildValue(int parentIndex) {
        return element[getRightChildIndex(parentIndex)];
    }

    private int parentValue(int parentIndex) {
        return element[parentIndex];
    }

    private int getParentData(int index) {
        return element[getParentIndex(index)];
    }

    private boolean hasLeftChild(int index) { // 배열이기때문에 음수 값도 들어갈수 있어서 값 대신 size로 비교
        return getLeftChildIndex(index) < size;
    }

    private boolean hasRightChild(int index) { // 배열이기때문에 음수 값도 들어갈수 있어서 값 대신 size로 비교
        return getRightChildIndex(index) < size;
    }

    @Override
    public boolean hasParent(int index) {
        return getParentIndex(index) >= 1;
    }

    private void swap(int targetIndex, int otherIndex) {
        int temp = element[targetIndex];
        element[targetIndex] = element[otherIndex];
        element[otherIndex] = temp;
    }

    private void validateSizeAndResize() {
        if (size == this.maxSize) {
            element = Arrays.copyOf(element, maxSize * 2);
            maxSize *= 2;
        }
    }

    public ArrayMinHeap(int maxSize) {
        this.maxSize = maxSize;
        this.element = new int[maxSize + 1];
        Arrays.fill(element, Integer.MAX_VALUE);
        this.size = 0;
    }

    @Override
    public void add(int data) {
        validateSizeAndResize();

        this.element[++size] = data;
        heapifyUpUseWhile(); // or heapifyUpUseFor();
    }

    // insert 할때는 마지막 인덱스부터 루트 인덱스(1) 까지 bottom-up 방식으로 크기를 비교해서 재구성 한다.
    // min heap은 작은값이 부모가 되야한다.
    private void heapifyUpUseFor() {
        for (int i = size; i > 1; i--) {
            int parentIndex = getParentIndex(i);

            if (hasParent(i) && element[parentIndex] > element[i]) {
                swap(parentIndex, i);
            }
        }
    }

    private void heapifyUpUseWhile() {
        int childIndex = size;

        while (hasParent(childIndex) && getParentData(childIndex) > element[childIndex]) {
            swap(getParentIndex(childIndex), childIndex);
            childIndex = getParentIndex(childIndex);
        }
    }

    @Override
    public int pop() {
        if (size == 0) {
            throw new ArrayIndexOutOfBoundsException("heap is empty");
        }

        int root = element[1];

        element[1] = element[size];
        element[size] = 0;
        this.size = size - 1;

        heapifyDownUseFor();// or heapifyDownUserWhile();

        return root;
    }

    private void heapifyDownUseFor() {
        for (int parent = 1; hasLeftChild(parent); ) {

            if (parentValue(parent) < leftChildValue(parent) && parentValue(parent) < rightChildValue(parent)) {
                break;

            } else if (leftChildValue(parent) < rightChildValue(parent)) {
                swap(parent, getLeftChildIndex(parent));
                parent = parent * 2;
            } else {
                swap(parent, getRightChildIndex(parent));
                parent = parent * 2 + 1;
            }

        }
    }

    // 자식 값중 더 작은 값을 교체해줘야 한다.
    public void heapifyDownUserWhile() {

        int parent = 1;

        while (hasLeftChild(parent)) {

            int smallIndex = smallerOfTheChildren(parent);

            if (hasRightChild(parent) && rightChildValue(parent) < leftChildValue(parent)) {
                smallIndex = getRightChildIndex(parent);
            }

            if (element[parent] < element[smallIndex]) {
                break;
            }

            swap(parent, smallIndex);
            parent = smallIndex;

        }
    }

    private int smallerOfTheChildren(int parentIndex) {

        if (hasLeftChild(parentIndex) && leftChildValue(parentIndex) < rightChildValue(parentIndex)) {
            return getLeftChildIndex(parentIndex);
        } else {
            return getRightChildIndex(parentIndex);
        }
    }

    @Override
    public void printElements() {
        if (this.size == 0) {
            return;
        }

        while (!(this.size == 0)) {
            System.out.print(pop() + ", ");
        }
    }

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


    @Override
    public int peek() {
        return element[1];
    }

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

    public static void main(String[] args) {
        ArrayMinHeap arrayMinHeap = new ArrayMinHeap(10);

        arrayMinHeap.add(5);
        arrayMinHeap.add(4);
        arrayMinHeap.add(2);
        arrayMinHeap.add(7);
        arrayMinHeap.add(8);
        arrayMinHeap.add(9);
        arrayMinHeap.add(3);
        arrayMinHeap.add(6);
        arrayMinHeap.add(15);
        arrayMinHeap.add(999);
        arrayMinHeap.add(2134134);
        arrayMinHeap.add(21);
        arrayMinHeap.add(1);
        arrayMinHeap.add(9918324);
        arrayMinHeap.add(239328);
        arrayMinHeap.add(8237237);
        arrayMinHeap.add(99999999);

        arrayMinHeap.printElements();
    }
}

• [힙(Heap)](https://github.com/gyoogle/tech-interview-for-developer/blob/master/Computer Science/Data Structure/Heap.md)

• [Data Structure] Heap](https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Data Structure/[Data Structure] Heap.md)

• [Binary Heap](