[Java] 자바로 Deap 구현하기

 

 

 

Deap이란?

https://ttl-blog.tistory.com/712

[자료구조] - 딥(Deap)

 

 

 

 

 

 

 

 

 

 

 

Deap 인터페이스

public interface Deap <E extends Comparable<E>> {


   int getLevel(int idx);
   boolean isMaxPosition(int idx);
   boolean isMinPosition(int idx);

   int getMaxPartnerIdx(int minIdx);
   int getMinPartnerIdx(int maxIdx);


   boolean add(E e);
   E removeMax();
   E removeMin();

   boolean isFull();
   boolean isEmpty();
   void levelOrder();


}

 

 

 

 

 

 

 

 

 

세부 구현

 

기본 필드

public class DeapImpl<E extends Comparable<E>> implements Deap<E>{
   private static final int NULL_ROOT = 1;
   private static final int MIN_ROOT = 2;
   private static final int MAX_ROOT = 3;
   private static final int DEFAULT_CAPACITY = 100;

   private E[] deap;
   private int size;
   private int capacity;

   public DeapImpl() {
      this.deap = (E[]) new Comparable[DEFAULT_CAPACITY + 2];//인덱스 0은 사용하지 않고, ROOT는 0을 사용하므로 + 2
      this.capacity = DEFAULT_CAPACITY;
   }

설명

기본적으로 트리를 구현할 때, ROOT 노드를 1로 설정하였습니다.

그러나 deap은 ROOT를 사용하지 않습니다.

즉 배열 중 0과 1은 사용하지 않기에 용량 + 2 만큼의 사이즈로 배열을 생성해 줍니다.

 

MIN_ROOT는 Min Heap의 ROOT이며, 

MAX_ROOT는 Max Heap의 ROOT입니다.

 

 

 

 

레벨 구하기

/**
 * 루트 노드의 인덱스를 1로 했을 때,
 * 인덱스 n의 레벨 -> [log_2(n)] + 1
 * @param idx 인덱스
 * @return 레벨
 */
@Override
public int getLevel(int idx) {
   return (int)(Math.log(idx) / Math.log(2)) + 1;
}

주석 혹은 해당 글 상단의 'Deap이란?' 을 참고해주세요

 

 

 

 

 

 

레벨 i의 시작 인덱스 구하기

/**
 * 레벨 i의 시작 인덱스는
 * 이전 레벨의 총 노드 수인 2^{i-1} -1에 1을 더한
 * 2^{i-1}
 */
public int getStartIdxOfLevel(int level) {
   if (level == 1 || level == 2) return level;
   return (int)Math.pow(2, level - 1);//2^{level - 1}
}

 

 

 

 

속하는 Heap 판별하기

/**
 * 레벨 i에 존재할 수 있는 노드의 수는 2^{i-1}개임
 * 이때 Max Part 의 길이는 절반이므로 2로 나눈 2^{i-1}개
 * 즉 레벨 i의 시작 인덱스 + 2^{i-1}
 */
public int getStartIdxOfMaxHeapOfLevel(int level) {
   return getStartIdxOfLevel(level) + (int)Math.pow(2, level - 2);
}

@Override
public boolean isMaxPosition(int idx) {
   int level = getLevel(idx);
   return (getStartIdxOfMaxHeapOfLevel(level) <= idx);
}

@Override
public boolean isMinPosition(int idx) {
   int level = getLevel(idx);
   return (getStartIdxOfLevel(level) <= idx) && (idx < getStartIdxOfMaxHeapOfLevel(level));
}

 

 

 

 

 

 

 

대응하는 파트너 찾기

/**
 * i의 max Partner 인덱스 -> 동일 레벨에 존재할 경우
 * 레벨을 n이라 하면 = i + 2^{n-2}
 * 동일 레벨에 존재하지 않을 경우 이의 부모 = (i + 2^{i-2}) / 2
 */
@Override
public int getMaxPartnerIdx(int minIdx) {
   if (minIdx == 0 || minIdx == 1 || isMaxPosition(minIdx)) return 0;
   if (minIdx == MIN_ROOT) return (deap[MAX_ROOT] == null) ? 0 : MAX_ROOT;

   int level = getLevel(minIdx);
   int maxPartnerIdx = (int)Math.pow(2, level - 2) + minIdx;

   if (deap[maxPartnerIdx] == null) {
      return maxPartnerIdx / 2;
   }
   return maxPartnerIdx;
}


/**
 * i의 min Partner 인덱스 -> 동일 레벨에 존재할 경우
 * 레벨을 n이라 하면 = i - 2^{n-2}
 * 동일 레벨에 존재하지 않을 경우 이의 부모 = (i - 2^{i-2}) / 2
 */
@Override
public int getMinPartnerIdx(int maxIdx) {
   if (maxIdx == 0 || maxIdx == 1 || maxIdx == 2 || isMinPosition(maxIdx)) return 0;
   if (maxIdx == MAX_ROOT) return MIN_ROOT;

   int level = getLevel(maxIdx);
   return  maxIdx - (int)Math.pow(2, level - 2);//완전 이진트리이므로 Min partner 는 반드시 존재

}

 

 

 

 

 

 

 

주어진 인덱스로부터 최소 힙 만들기

/**
 * lastIdx 부터 시작해서 부모와 비교
 * 부모보다 작다면 위치 변경
 */
private void minHeapify(int lastIdx) {

   while (lastIdx > MIN_ROOT) {
      E child = this.deap[lastIdx];
      E parent = this.deap[lastIdx/2];

      if (child.compareTo(parent) < 0) {
         swap(lastIdx, lastIdx/2);
         lastIdx /= 2;
      }
      else {return;}
   }

}

 

 

 

 

 

 

 

주어진 인덱스로부터 최대 힙 만들기

/**
 * lastIdx 부터 시작해서 부모와 비교
 * 부모보다 크다면 위치 변경
 */
private void maxHeapify(int lastIdx) {
   while (lastIdx > MAX_ROOT) {
      E child = this.deap[lastIdx];
      E parent = this.deap[lastIdx/2];

      if (child.compareTo(parent) > 0) {
         swap(lastIdx, lastIdx/2);
         lastIdx /= 2;
      }
      else {return;}
   }

}

 

 

 

 

 

 

 

 

 

 

 

 

값 추가하기

@Override
public boolean add(E element) {
   if (isFull()) grow();

   if (isEmpty()) {
      size ++;
      this.deap[MIN_ROOT] = element;
      return true;
   }

   size ++;
   int addIdx = size + 1;//배열의 0번은 사용하지 않고, 배열의 1번은 NULL ROOT 이므로, 사이즈가 1일때는 인덱스 2에 삽입되어야 한다.
   this.deap[addIdx] = element;

   if (isMinPosition(addIdx)) {
      int maxPartnerIdx = getMaxPartnerIdx(addIdx);//비어있는 경우 저절로 부모 반환하게 해둠
      E maxPartner = deap[maxPartnerIdx];
      if (element.compareTo(maxPartner) > 0) {//Min Heap의 원소가 Max Heap보다 클 때
         swap(addIdx,maxPartnerIdx);
         maxHeapify(maxPartnerIdx);
      }
      else {
         minHeapify(addIdx);
      }
      return true;
   }

   int minPartnerIdx = getMinPartnerIdx(addIdx);
   E minPartner = deap[minPartnerIdx];
   if (element.compareTo(minPartner) < 0) {
      swap(addIdx,minPartnerIdx);
      minHeapify(minPartnerIdx);
   }
   else {
      maxHeapify(addIdx);
   }
   return true;
}

 

설명

1. 원소를 가장 마지막 위치에 삽입합니다.

2. 삽입된 위치가 Max Heap에 속하는지 Min Heap에 속하는지 확인합니다.


3. Min Heap에 속하는 경우 대응되는 Max Heap의 원소와 비교합니다.
(Max Heap에 속하는 경우 3,4,5번의 과정에서 Min과 Max를 반대로 진행합니다.)

4. Max Heap의 원소보다 작은 경우 삽입된 위치의 부모와 비교해가며 망가진 Min Heap을 복구합니다.

5. Max Heap의 원소보다 큰 경우 두 원소를 교체한 후, 교체한 Max Heap의 위치에서 망가진 Max Heap을 복구합니다

 

Max Heap에 삽입

 

 

Min Heap에 삽입

 

 

 

 

 

 

 

 

최솟값 삭제하기

@Override
public E removeMin() {
   if (isEmpty()) return null;
   E remove = this.deap[MIN_ROOT];

   int currentIdx = MIN_ROOT;

   while (hasChild(currentIdx)){
      int minChildIdx = getMinChildIdx(currentIdx);
      this.deap[currentIdx] = this.deap[minChildIdx];
      currentIdx = minChildIdx;
   }

   int lastNodeIdx = this.size + 1;//1번 루트를 사용하지 않으므로 +1



   deap[currentIdx] = deap[lastNodeIdx];//마지막 노드를 빈공간으로 가져옴
   deap[lastNodeIdx] = null;//마지막 노드를 삭제해줌
   this.size --;

   if (isMaxPosition(lastNodeIdx)) {//마지막 노드가 Max 부분인 경우에 문제 발생

      //마지막 노드가 잘 삽입되었는지 확인해야함
      //우선 빈공간(currentIdx)을 마지막 노드의 값으로 채웠으므로 currentIdx의 Maxpartner와 비교해야 함
      //비교해서 currentIdx가 더 크다면 위치를 바꿔주고 망가진 maxHeap 복구
      //아니라면 종료
      int maxPartnerIdx = getMaxPartnerIdx(currentIdx);
      if (deap[currentIdx].compareTo(deap[maxPartnerIdx]) > 0 ){
         swap(currentIdx, maxPartnerIdx);
         maxHeapify(maxPartnerIdx);
      }
   }
   minHeapify(currentIdx);//Min Heap 복구

   return remove;
}

설명

1. Min Heap의 루트를 제거합니다. 이 값이 최댓값입니다.

2. Min Heap의 루트로부터 시작하여 다음을 반복합니다.

3. 자식 노드를 확인합니다. 존재한다면 자식들 중 더 작은 값을 자신의 위치로 옮깁니다.

4. 이후 자신의 인덱스를 자식의 인덱스로 바꾸어줍니다.

5. 자식 노드가 존재하지 않는다면 반복을 종료합니다.


6. 반복을 종료한 뒤, 가장 마지막 노드를 마지막 위치 자리에서 제거하며, 현재 위치로 옮겨줍니다.

7. Deap이 망가졌으므로 복구를 진행해야 합니다.
아래는 복구하는 과정입니다.

9. 마지막 노드가 삽입된 현재 위치에서 대응되는 Max Heap의 원소와 비교합니다.

10. 현재 위치(Min Heap)의 원소가 Max Heap의 원소보다 크다면 이를 교체해준 후, 망가진 두 Heap을 복구합니다.(이는 삽입과 동일한 과정입니다.)

11. 현재 위치(Min Heap)의 원소가 Max Heap의 원소보다 작지 않다면 망가진 Min-Heap을 복구합니다.

 

 

마지막 노드가 Max Heap에 존재하는 경우

 

 

마지막 노드가 Min Heap에 존재하는 경우

 

 

 

 

 

 

 

 

 

최댓값 삭제하기

@Override
public E removeMax() {
   if (isEmpty()) return null;
   if (this.size == 1) {
      size--;
      return this.deap[MIN_ROOT];
   }

   E remove = this.deap[MAX_ROOT];

   int currentIdx = MAX_ROOT;

   while (hasChild(currentIdx)){
      int maxChildIdx = getMaxChildIdx(currentIdx);
      this.deap[currentIdx] = this.deap[maxChildIdx];
      currentIdx = maxChildIdx;
   }

   int lastNodeIdx = this.size + 1;//1번 루트를 사용하지 않으므로 +1



   deap[currentIdx] = deap[lastNodeIdx];//currentIdx 가 lastNodeIdx 같아도 상관없다.
   deap[lastNodeIdx] = null;
   this.size --;


   if (isMinPosition(lastNodeIdx)) {//마지막 노드가 Min 부분인 경우에 문제 발생

      //마지막 노드가 잘 삽입되었는지 확인해야함
      //우선 빈공간(currentIdx)을 마지막 노드의 값으로 채웠으므로 currentIdx의 Minpartner와 비교해야 함
      //비교해서 currentIdx가 더 작다면 위치를 바꿔주고 망가진 minHeap 복구
      //비교해서 currentIdx가 더 작지 않다면 바로 종료
      int minPartnerIdx = getMinPartnerIdx(currentIdx);
      if (deap[currentIdx].compareTo(deap[minPartnerIdx]) < 0 ){
         swap(currentIdx, minPartnerIdx);
         minHeapify(minPartnerIdx);
      }
   }
   maxHeapify(currentIdx);
   
   return remove;
}

 

 

 

 

 

 

 

 

 

전체 코드

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;


public class DeapImpl<E extends Comparable<E>> implements Deap<E>{
   private static final int NULL_ROOT = 1;
   private static final int MIN_ROOT = 2;
   private static final int MAX_ROOT = 3;
   private static final int DEFAULT_CAPACITY = 100;

   private E[] deap;
   private int size;
   private int capacity;

   public DeapImpl() {
      this.deap = (E[]) new Comparable[DEFAULT_CAPACITY + 2];//인덱스 0은 사용하지 않고, ROOT는 0을 사용하므로 + 2
      this.capacity = DEFAULT_CAPACITY;
   }

   //== 용량 2배 늘리기 ==//
   private void grow() {
      this.capacity *= 2;
      this.deap = Arrays.copyOf(this.deap, this.capacity + 2);
   }




   /**
    * 루트 노드의 인덱스를 1로 했을 때,
    * 인덱스 n의 레벨 -> [log_2(n)] + 1
    * @param idx 인덱스
    * @return 레벨
    */
   @Override
   public int getLevel(int idx) {
      return (int)(Math.log(idx) / Math.log(2)) + 1;
   }


   /**
    * 레벨 i의 시작 인덱스는
    * 이전 레벨의 총 노드 수인 2^{i-1} -1에 1을 더한
    * 2^{i-1}
    */
   public int getStartIdxOfLevel(int level) {
      if (level == 1 || level == 2) return level;
      return (int)Math.pow(2, level - 1);//2^{level - 1}
   }



   /**
    * 레벨 i에 존재할 수 있는 노드의 수는 2^{i-1}개임
    * 이때 Max Part 의 길이는 절반이므로 2로 나눈 2^{i-1}개
    * 즉 레벨 i의 시작 인덱스 + 2^{i-1}
    */
   public int getStartIdxOfMaxHeapOfLevel(int level) {
      return getStartIdxOfLevel(level) + (int)Math.pow(2, level - 2);
   }


   @Override
   public boolean isMaxPosition(int idx) {
      int level = getLevel(idx);
      return (getStartIdxOfMaxHeapOfLevel(level) <= idx);
   }

   @Override
   public boolean isMinPosition(int idx) {
      int level = getLevel(idx);
      return (getStartIdxOfLevel(level) <= idx) && (idx < getStartIdxOfMaxHeapOfLevel(level));
   }













   /**
    * i의 max Partner 인덱스 -> 동일 레벨에 존재할 경우
    * 레벨을 n이라 하면 = i + 2^{n-2}
    * 동일 레벨에 존재하지 않을 경우 이의 부모 = (i + 2^{i-2}) / 2
    */
   @Override
   public int getMaxPartnerIdx(int minIdx) {
      if (minIdx == 0 || minIdx == 1 || isMaxPosition(minIdx)) return 0;
      if (minIdx == MIN_ROOT) return (deap[MAX_ROOT] == null) ? 0 : MAX_ROOT;

      int level = getLevel(minIdx);
      int maxPartnerIdx = (int)Math.pow(2, level - 2) + minIdx;

      if (maxPartnerIdx >= this.deap.length||deap[maxPartnerIdx] == null) {
         return maxPartnerIdx / 2;
      }
      return maxPartnerIdx;
   }


   /**
    * i의 min Partner 인덱스 -> 동일 레벨에 존재할 경우
    * 레벨을 n이라 하면 = i - 2^{n-2}
    * 동일 레벨에 존재하지 않을 경우 이의 부모 = (i - 2^{i-2}) / 2
    */
   @Override
   public int getMinPartnerIdx(int maxIdx) {
      if (maxIdx == 0 || maxIdx == 1 || maxIdx == 2 || isMinPosition(maxIdx)) return 0;
      if (maxIdx == MAX_ROOT) return MIN_ROOT;

      int level = getLevel(maxIdx);
      return  maxIdx - (int)Math.pow(2, level - 2);//완전 이진트리이므로 Min partner 는 반드시 존재

   }





   @Override
   public boolean add(E element) {
      if (isFull()) grow();

      if (isEmpty()) {
         size ++;
         this.deap[MIN_ROOT] = element;
         return true;
      }

      size ++;
      int addIdx = size + 1;//배열의 0번은 사용하지 않고, 배열의 1번은 NULL ROOT 이므로, 사이즈가 1일때는 인덱스 2에 삽입되어야 한다.
      this.deap[addIdx] = element;

      if (isMinPosition(addIdx)) {
         int maxPartnerIdx = getMaxPartnerIdx(addIdx);//비어있는 경우 저절로 부모 반환하게 해둠
         E maxPartner = deap[maxPartnerIdx];
         if (element.compareTo(maxPartner) > 0) {//Min Heap의 원소가 Max Heap보다 클 때
            swap(addIdx,maxPartnerIdx);
            maxHeapify(maxPartnerIdx);
         }
         else {
            minHeapify(addIdx);
         }
         return true;
      }

      int minPartnerIdx = getMinPartnerIdx(addIdx);
      E minPartner = deap[minPartnerIdx];
      if (element.compareTo(minPartner) < 0) {
         swap(addIdx,minPartnerIdx);
         minHeapify(minPartnerIdx);
      }
      else {
         maxHeapify(addIdx);
      }
      return true;
   }

   /**
    * lastIdx 부터 시작해서 부모와 비교
    * 부모보다 작다면 위치 변경
    */
   private void minHeapify(int lastIdx) {

      while (lastIdx > MIN_ROOT) {
         E child = this.deap[lastIdx];
         E parent = this.deap[lastIdx/2];

         if (child.compareTo(parent) < 0) {
            swap(lastIdx, lastIdx/2);
            lastIdx /= 2;
         }
         else {return;}
      }

   }


   /**
    * lastIdx 부터 시작해서 부모와 비교
    * 부모보다 크다면 위치 변경
    */
   private void maxHeapify(int lastIdx) {
      while (lastIdx > MAX_ROOT) {
         E child = this.deap[lastIdx];
         E parent = this.deap[lastIdx/2];

         if (child.compareTo(parent) > 0) {
            swap(lastIdx, lastIdx/2);
            lastIdx /= 2;
         }
         else {return;}
      }

   }




   private void swap(int i1, int i2) {
      E temp = deap[i1];
      deap[i1] = deap[i2];
      deap[i2] = temp;
   }




   @Override
   public E removeMax() {
      if (isEmpty()) return null;
      if (this.size == 1) {
         size--;
         return this.deap[MIN_ROOT];
      }

      E remove = this.deap[MAX_ROOT];

      int currentIdx = MAX_ROOT;

      while (hasChild(currentIdx)){
         int maxChildIdx = getMaxChildIdx(currentIdx);
         this.deap[currentIdx] = this.deap[maxChildIdx];
         currentIdx = maxChildIdx;
      }

      int lastNodeIdx = this.size + 1;//1번 루트를 사용하지 않으므로 +1



      deap[currentIdx] = deap[lastNodeIdx];//currentIdx 가 lastNodeIdx 같아도 상관없다.
      deap[lastNodeIdx] = null;
      this.size --;


      if (isMinPosition(lastNodeIdx)) {//마지막 노드가 Min 부분인 경우에 문제 발생

         //마지막 노드가 잘 삽입되었는지 확인해야함
         //우선 빈공간(currentIdx)을 마지막 노드의 값으로 채웠으므로 currentIdx의 Minpartner와 비교해야 함
         //비교해서 currentIdx가 더 작다면 위치를 바꿔주고 망가진 minHeap 복구
         //비교해서 currentIdx가 더 작지 않다면 바로 종료
         int minPartnerIdx = getMinPartnerIdx(currentIdx);
         if (deap[currentIdx].compareTo(deap[minPartnerIdx]) < 0 ){
            swap(currentIdx, minPartnerIdx);
            minHeapify(minPartnerIdx);
         }

      }
      maxHeapify(currentIdx);
      return remove;
   }




   private int getMaxChildIdx(int currentIdx) {
      int leftChildIdx = currentIdx * 2;
      int rightChildIdx = currentIdx * 2 + 1;
      E leftChild = this.deap[leftChildIdx];
      E rightChild = this.deap[rightChildIdx];

      return (rightChild == null || leftChild.compareTo(rightChild) > 0)
         ?  leftChildIdx
         : rightChildIdx;
   }

   @Override
   public E removeMin() {
      if (isEmpty()) return null;
      E remove = this.deap[MIN_ROOT];

      int currentIdx = MIN_ROOT;

      while (hasChild(currentIdx)){
         int minChildIdx = getMinChildIdx(currentIdx);
         this.deap[currentIdx] = this.deap[minChildIdx];
         currentIdx = minChildIdx;
      }

      int lastNodeIdx = this.size + 1;//1번 루트를 사용하지 않으므로 +1



      deap[currentIdx] = deap[lastNodeIdx];//마지막 노드를 빈공간으로 가져옴
      deap[lastNodeIdx] = null;//마지막 노드를 삭제해줌
      this.size --;

      if (isMaxPosition(lastNodeIdx)) {//마지막 노드가 Max 부분인 경우에 문제 발생

         //마지막 노드가 잘 삽입되었는지 확인해야함
         //우선 빈공간(currentIdx)을 마지막 노드의 값으로 채웠으므로 currentIdx의 Maxpartner와 비교해야 함
         //비교해서 currentIdx가 더 크다면 위치를 바꿔주고 망가진 maxHeap 복구
         //아니라면 종료
         int maxPartnerIdx = getMaxPartnerIdx(currentIdx);
         if (deap[currentIdx].compareTo(deap[maxPartnerIdx]) > 0 ){
            swap(currentIdx, maxPartnerIdx);
            maxHeapify(maxPartnerIdx);
         }
      }
      minHeapify(currentIdx);
      return remove;
   }


   private int getMinChildIdx(int currentIdx) {
      int leftChildIdx = currentIdx * 2;
      int rightChildIdx = currentIdx * 2 + 1;
      E leftChild = this.deap[leftChildIdx];
      E rightChild = this.deap[rightChildIdx];

      return (rightChild == null || leftChild.compareTo(rightChild) < 0)
         ?  leftChildIdx
         : rightChildIdx;

   }

   private boolean hasChild(int currentIdx) {
      if (currentIdx * 2 >= this.deap.length)return false;
      return this.deap[currentIdx * 2] != null;
   }



   @Override
   public boolean isFull() {
      return size == this.capacity;
   }

   @Override
   public boolean isEmpty() {
      return size == 0;
   }

   @Override
   public void levelOrder() {
      if (isEmpty()) return;
      if (size == 1) {
         System.out.println(deap[MIN_ROOT]);
         return;
      }

      Deque<Integer> deque = new ArrayDeque<>();

      deque.add(MIN_ROOT);
      deque.add(MAX_ROOT);

      int currentIdxLevel = 1;
      int prevIdxLevel= 1;

      while (!deque.isEmpty()) {
         Integer current = deque.poll();

         printLevel(current);

         printBar(current);

         System.out.print("["+deap[current]+"]");
         if (hasLeftChild(current)){
            deque.add(current * 2);
         }
         if (hasRightChild(current)){
            deque.add(current * 2 + 1);
         }
      }
      System.out.println("\n\n종료----------------\n\n");

   }

   private boolean hasRightChild(Integer current) {
      if (current * 2 + 1 >= this.deap.length) return false;
      return deap[current * 2 + 1] != null;
   }

   private boolean hasLeftChild(Integer current) {
      if (current * 2 >= this.deap.length) return false;
      return deap[current * 2] != null;
   }

   private void printBar(Integer current) {
      if (isMinPosition(current - 1) && isMaxPosition(current )){
         System.out.print(" | ");
      }
   }

   private void printLevel(Integer current) {
      int prevIdxLevel;
      int currentIdxLevel;
      currentIdxLevel = getLevel(current);
      prevIdxLevel = getLevel(current - 1);

      if(currentIdxLevel != prevIdxLevel) {
         System.out.print("\nLEVEL [%d] :  ".formatted(currentIdxLevel));
      }
   }


}

 

 

 

 

 

 

 

 

 

 

테스트코드

 

삽입 테스트

코드

public class Test {
   public static void main(String[] args) {
      DeapImpl<Integer> deap = new DeapImpl<>();

      deap.add(5);
      deap.add(45);
      deap.add(10);
      deap.add(8);
      deap.add(25);
      deap.add(40);
      deap.add(15);
      deap.add(19);
      deap.levelOrder();

      System.out.println();
      System.out.println("삽입 후");
      deap.add(3);
      deap.levelOrder();




   }
}

 

 

 

 

 

 

 

 

 

 

코드

public class Test {
   public static void main(String[] args) {
      DeapImpl<Integer> deap = new DeapImpl<>();

      deap.add(5);
      deap.add(45);
      deap.add(10);
      deap.add(8);
      deap.add(25);
      deap.add(40);
      deap.add(15);
      deap.add(19);
      deap.add(9);
      deap.add(30);
      deap.add(20);
      deap.levelOrder();

      System.out.println();
      System.out.println("삽입 후");
      deap.add(4);
      deap.levelOrder();




   }
}

 

 

 

 

 

삭제 테스트

코드

public class Test {
   public static void main(String[] args) {
      DeapImpl<Integer> deap = new DeapImpl<>();

      deap.add(5);
      deap.add(65);
      deap.add(10);
      deap.add(8);
      deap.add(45);
      deap.add(35);
      deap.add(15);
      deap.add(19);
      deap.add(9);
      deap.add(30);
      deap.add(40);
      deap.levelOrder();

      System.out.println();
      System.out.println("삭제 후");
      deap.removeMin();
      deap.levelOrder();




   }
}

 

 

 

 

 

코드

public class Test {
   public static void main(String[] args) {
      DeapImpl<Integer> deap = new DeapImpl<>();

      deap.add(5);
      deap.add(65);
      deap.add(10);
      deap.add(8);
      deap.add(45);
      deap.add(35);
      deap.add(15);
      deap.add(19);
      deap.add(9);
      deap.add(30);
      deap.levelOrder();

      System.out.println();
      System.out.println("삭제 후");
      deap.removeMin();
      deap.levelOrder();




   }
}