[Java] 자바로 Heap 구현하기

 

 

 

 

 

Heap이란?

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

[자료구조] - 힙(Heap)

 

 

 

 

 

 

 

 

 

 

 

 

Heap 인터페이스

public interface Heap<E> {

   boolean isFull();
   boolean isEmpty();

   void levelOrder();

   boolean add(E e);
   E remove();
}

 

 

 

 

 

 

 

 

 

 

세부 구현

 

 

기본 필드

public class MaxHeap<E extends Comparable<E>> implements Heap<E>{


   private static final int DEFAULT_CAPACITY = 1;
   private static final int ROOT = 1;
   private int size;
   private int capacity;

   private E[] heap;

   @SuppressWarnings("unchecked")
   public MaxHeap(int capacity) {
      this.capacity = capacity;
      this.heap = (E[]) new Comparable[capacity+1];
      //ROOT 를 1로 설정할 것이기에 크기를 1 더
      //E extends Comparable<E> 때문에 Object 가 아닌 Comparable
   }

   public MaxHeap() {
      this(DEFAULT_CAPACITY);
   }

ROOT의 인덱스를 1로 정의하겠습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

자식 & 부모 인덱스 구하기

//== 자식 & 부모 인덱스 반환 ==//
private int rightChildIdx(int parentIdx) {
   return (parentIdx * 2) + 1;
}

private int leftChildIdx(int parentIdx) {
   return parentIdx * 2;
}

private int parentIdx(int currentIdx) {
   return currentIdx / 2;
}

설명

특정 노드의 인덱스가 n이라 할 때,

왼쪽 자식 인덱스
$$n \cdot 2$$

오른쪽 자식 인덱스
$$n \cdot 2 + 1$$

부모 인덱스
$$n \;/ \;2$$

 

 

 

 

 

 

 

 

 

 

 

 

 

자식 & 부모 존재여부 확인

//== 자식 & 부모의 존재여부 확인 ==//
private boolean hasLeft(int parentIdx) {
   // < 이면 안된다, <= 이어야 한다
   return (leftChildIdx(parentIdx) <= this.capacity) &&  this.heap[leftChildIdx(parentIdx)] != null;
}

private boolean hasRight(int parentIdx) {
   return (rightChildIdx(parentIdx)<= this.capacity) &&  this.heap[rightChildIdx(parentIdx)] != null;
}

private boolean hasParent(int childIdx) {
   return (parentIdx(childIdx) >= ROOT);
}

private boolean hasChild(int currentIdx) {
   return (currentIdx * 2 <= this.capacity) && (heap[currentIdx*2] != null);
}

설명

capacity에 =가 들어가는 이유:

간단하게 capacity가 2인 경우 생각

 

 

 

 

 

 

 

 

 

 

 

 

Heap에 값 추가

public boolean add(E e) {
   if (isFull()) grow();

   size++;
   heap[size] = e;//삽입하려는 노드를 가장 마지막에 추가

   int currentIdx = size;

   while (hasParent(currentIdx)) {//부모가 존재하는 경우 반복

      int parentIdx = parentIdx(currentIdx);

      E current = heap[currentIdx];
      E parent = heap[parentIdx];

      //== 부모가 더 크다면 Max Heap 만족 -> 반복 종료 ==//
      if (parent.compareTo(current) >= 0) {break;}

      //== 부모가 더 작다면 위치 변경 ==//
      if (parent.compareTo(current) < 0) {swap(parentIdx, currentIdx);}

      currentIdx = parentIdx;
   }
   return true;
}

 

설명

힙의 삽입 방법

삽입하려는 노드를 가장 마지막에 추가합니다.

이로 인해 힙이 망가졌으므로 다음을 통해 복구합니다.

삽입된 노드 즉, Heap의 마지막 노드에서부터 다음을 반복합니다.

1. 부모 노드를 확인합니다.  만약 존재하지 않는다면 반복을 종료합니다.
2. 부모 노드가 존재한다면, 부모 노드보다 작거나 같은 경우 해당 위치가 올바르게 삽입된 위치이므로 반복을 종료합니다.
3. 만약 부모 노드보다 큰 경우 부모노드와 위치를 바꾼 후 다시 바꾼 위치의 부모 노드와 비교하는 작업을 반복합니다.

 

 

 

 

 

 

 

 

 

Heap에서 Root 제거

@Override
public E remove() {
   E remove = heap[ROOT];

   E last = heap[size];
   heap[size] = null;
   size--;

   heap[ROOT] = last;
   int currentIdx = ROOT;

   while (hasChild(currentIdx)) {

      //== 자식이 하나이거나 둘인 경우 -> 하나인 경우는 완전이진트리이므로 반드시 left Node 만 존재==//
      int biggerChildIdx = biggerChildIdx(currentIdx);

      E current = heap[currentIdx];
      E child = heap[biggerChildIdx];

      //== 자식보다 작은 경우에만 진행 ==//
      if (current.compareTo(child) >= 0 ) {break;}

      swap(biggerChildIdx, currentIdx);
      currentIdx = biggerChildIdx;
   }

   return remove;
}




private int biggerChildIdx(int currentIdx) {
   //== 호출되었을 때 반드시 child 는 존재하는 상황 ==//
   
   //== 만약 Right Child가 존재하지 않는다면, Left Child가 자식 중 가장 큰 값 ==//
   if (! hasRight(currentIdx)) return leftChildIdx(currentIdx);
   
   //== rightChild가 leftChild보다 큰 경우 rightChild의 인덱스 반환 ==//
   return (heap[rightChildIdx(currentIdx)].compareTo(heap[leftChildIdx(currentIdx)]) > 0) 
      ? rightChildIdx(currentIdx) 
      : leftChildIdx(currentIdx);
}

설명

힙의 루트 삭제 방법

루트 노드를 제거합니다.

이로 인해 힙이 망가졌으므로 다음을 통해 복구합니다.

Heap의 마지막 노드를 root의 위치로 가져옵니다.
이후 루트에서부터 다음을 반복합니다.

1. 자식이 존재하는지 확인합니다. 존재한다면 자식들 중 큰 값을 갖는 자식과 위치를 바꿉니다.
2. 자식이 존재하지만 자식의 값이 현재 값보다 작다면 반복을 종료합니다.
3. 자식이 존재하지 않는다면 반복을 종료합니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

MaxHeap 전체 코드

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

public class MaxHeap<E extends Comparable<E>> implements Heap<E>{


   private static final int DEFAULT_CAPACITY = 1;
   private static final int ROOT = 1;
   private int size;
   private int capacity;

   private E[] heap;

   @SuppressWarnings("unchecked")
   public MaxHeap(int capacity) {
      this.capacity = capacity;
      this.heap = (E[]) new Comparable[capacity+1];
      //ROOT 를 1로 설정할 것이기에 크기를 1 더
      //E extends Comparable<E> 때문에 Object 가 아닌 Comparable
   }

   public MaxHeap() {
      this(DEFAULT_CAPACITY);
   }

   private E[] heap() {
      return heap;
   }



   //== 자식 & 부모 인덱스 반환 ==//
   private int rightChildIdx(int parentIdx) {
      return (parentIdx * 2) + 1;
   }

   private int leftChildIdx(int parentIdx) {
      return parentIdx * 2;
   }

   private int parentIdx(int currentIdx) {
      return currentIdx / 2;
   }




   //== 자식 & 부모의 존재여부 확인 ==//
   private boolean hasLeft(int parentIdx) {
      // < 이면 안된다, <= 이어야 한다
      return (leftChildIdx(parentIdx) <= this.capacity) &&  this.heap[leftChildIdx(parentIdx)] != null;
   }

   private boolean hasRight(int parentIdx) {
      return (rightChildIdx(parentIdx)<= this.capacity) &&  this.heap[rightChildIdx(parentIdx)] != null;
   }

   private boolean hasParent(int childIdx) {
      return (parentIdx(childIdx) >= ROOT);
   }

   private boolean hasChild(int currentIdx) {
      return (currentIdx * 2 <= this.capacity) && (heap[currentIdx*2] != null);
   }




   //== 배열 값 교체 ==//
   private void swap(int parentIdx, int currentIdx) {
      E temp = heap[parentIdx];
      heap[parentIdx] = heap[currentIdx];
      heap[currentIdx] =  temp;
   }


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





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



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







   @Override
   public void levelOrder() {

      if (isEmpty()) return;
      Deque<Integer> deque = new ArrayDeque<>();
      deque.add(ROOT);

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

         System.out.print(" -> "+heap[poll]);

         if (hasLeft(poll)) {deque.add(poll * 2);}
         if (hasRight(poll)) {deque.add(poll * 2 + 1);}
      }
      System.out.println();

   }



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

      size++;
      heap[size] = e;//삽입하려는 노드를 가장 마지막에 추가

      int currentIdx = size;

      while (hasParent(currentIdx)) {//부모가 존재하는 경우 반복

         int parentIdx = parentIdx(currentIdx);

         E current = heap[currentIdx];
         E parent = heap[parentIdx];

         //== 부모가 더 크다면 Max Heap 만족 -> 반복 종료 ==//
         if (parent.compareTo(current) >= 0) {break;}

         //== 부모가 더 작다면 위치 변경 ==//
         if (parent.compareTo(current) < 0) {swap(parentIdx, currentIdx);}

         currentIdx = parentIdx;
      }
      return true;
   }


   @Override
   public E remove() {
      E remove = heap[ROOT];

      E last = heap[size];
      heap[size] = null;
      size--;

      heap[ROOT] = last;
      int currentIdx = ROOT;

      while (hasChild(currentIdx)) {

         //== 자식이 하나이거나 둘인 경우 -> 하나인 경우는 완전이진트리이므로 반드시 left Node 만 존재==//
         int biggerChildIdx = biggerChildIdx(currentIdx);

         E current = heap[currentIdx];
         E child = heap[biggerChildIdx];

         //== 자식보다 작은 경우에만 진행 ==//
         if (current.compareTo(child) >= 0 ) {break;}

         swap(biggerChildIdx, currentIdx);
         currentIdx = biggerChildIdx;
      }

      return remove;
   }




   private int biggerChildIdx(int currentIdx) {
      //== 호출되었을 때 반드시 child 는 존재하는 상황 ==//

      //== 만약 Right Child가 존재하지 않는다면, Left Child가 자식 중 가장 큰 값 ==//
      if (! hasRight(currentIdx)) return leftChildIdx(currentIdx);

      //== rightChild가 leftChild보다 큰 경우 rightChild의 인덱스 반환 ==//
      return (heap[rightChildIdx(currentIdx)].compareTo(heap[leftChildIdx(currentIdx)]) > 0)
         ? rightChildIdx(currentIdx)
         : leftChildIdx(currentIdx);
   }

}

 

 

 

 

 

 

 

 

 

 

 

 

테스트코드

public class Test {
   public static void main(String[] args) {

      MaxHeap<Integer> heap = new MaxHeap<>();



      heap.add(20);
      heap.add(15);
      heap.add(2);
      heap.add(14);
      heap.add(10);
      System.out.println("초기 상태");

      heap.levelOrder();
      

      System.out.println("\n삭제 수행\n"+heap.remove());
      System.out.println("\n삭제 후 상태");
      heap.levelOrder();


   }
}