[자료 구조] 힙(Heap)

자바(Java)예제로 구현한 힙(Heap) 자료 구조

힙(Heap) 이란 무었인가?

힙(Heap)은 완전 이진 트리(Complete Binary Tree)로, 각각의 노드가 자신의 부모 노드보다 작거나 같은 값을 저장하는 자료형 이다. 힙(Heap)은 완전 이진 트리(Complete Binary Tree)라 가장 아래에 있는 노드들을 제외한 모든 노드들이 두 자식 노드를 모두 가지고 있거나 아예 자식 노드를 가지지 않는 특성을 가진다.

• 만약 부모 노드가 자식 노드보다 크거나 같다면 그건 "Max Heap"(최대 힙)
• 부모 노드가 자식 노드보다 작거나 같다면 "Min Heap"(최소 힙) 이라 불린다.

힙(Heap) 컨셉

힙(Heap)은 실제로 어디에 사용될까?

• Heapsort(힙 정렬)
• 우선 순위 큐(Priority Queue)
• 힙 자료 구조는 우선 순위 큐를 구현하는데 많이 쓰인다
• 다양한 알고리즘(Algorithm) 구현

이진 힙(Binary Heap) 은 어떻게 구현되는가?

추상 자료형인 힙(Heap)은 매우 다양한 방법으로 구현될 수 있다. 가장 대중적인 힙 구현 방법은 Array를 이용하는 것이다. 우선 아래의 Big O 복잡도 표를 보고 가자

Operation	Big O Complexity
Insert	O(log n)
Remove Max	O(log n)
Fix Root	O(log n)

*중요한건, Array 를 이용한 이진 트리 구현에서, 인덱스 i 에 저장된 부모 노드의 두 자식 노드는 인덱스 (2*i)+1 와 (2*i)+2에 저장된다는걸 기억하자.

아래는 자바 배열(array)로 구현한 힙(Heap) 자료 구조 이다.

public class Heap {
 private int[] data;
 private int size;
 private int maximumSize;

 public Heap() {
  data = new int[100];
 }

 public static void main(String[] args) {
  int[] arr = new int[5];
  for (int i : arr) {
   System.out.println(i);
  }
 }

 public Heap(int maximumSize) {
  if (maximumSize < 1) {
   this.maximumSize = 100;
  } else {
   this.maximumSize = maximumSize;
  }
  this.maximumSize = maximumSize;
 }

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

 public boolean isFull() {
  return size == 100;
 }

 public void clear() {
  data = null;
 }

 // 새로운 데이터를 삽입
 public void insert(int newInt) {
  int pointer;// 어레이의 인덱스를 가리키는 포인터 이다.
  if (isFull()) {
   throw new FullHeapException();
   // 힙이 꽉 차있다면 Exception(예외) 처리를 해주자
  } else {
   // 아니면 배열의 끝에 새로운 데이터를 삽입한다.
   data[size] = newInt;
   pointer = size;
   size++;

   while (pointer > 0 && data[pointer] > data[(pointer - 1) / 2]) {
    // 최대 힙에서 자식 노드는 무조건 부모 노드보다 작거나 같아야한다
    // 그러니 끝에 삽입된 노드를 부모 노드와 비교해서 크다면 부모 노드와 교체해주자
    int temp = data[pointer];
    data[pointer] = data[(pointer - 1) / 2];
    data[(pointer - 1) / 2] = temp;
    pointer = (pointer - 1) / 2;
   }
  }
 }
 
 // 힙에서 노드를 제거
 // 힙에서 제거 메소드는 가장 큰 노드 1개, 즉 루트 노드를 제거하고 반환한다.
 public int remove() {
  int toReturn;//리턴될 인스턴스
  if (!isEmpty()) {
   toReturn = data[0];
   // 어레이의 가장 끝에 존재하는 노드를 루트 노드에 집어넣는다
   data[0] = data[--size];
   data[size] = 0;
  } else {
   // 만약 힙이 텅 빈 상태라면 예외 처리를 해주자
   throw new EmptyHeapException();
  }

  // 어레이의 가장 끝에 있는 노드를 루트 노드에 넣었으니, 힙을 재정렬 해야한다.
  fixRoot();//재정렬 메소드를 실행하자

  return toReturn;//toReturn 인스턴스에 저장된 값을 반환한다.

 }

 public void fixRoot() {
  // remove 메소드에서 가장 큰 노드,즉 루트 노드를 제거하고 그 자리에 가장 끝에 있는 노드를 삽입했다.
  // 다시 힙을 재정렬 함으로써 루트 노드가 적절값을 가지도록 해야한다.

  int pointer = 0;//루트 노드에서 시작한다
  while (pointer * 2 + 1 < size) {
   // 자식 노드중 더 큰 노드와 자리를 교체한다.
   if (data[pointer * 2 + 1] > data[pointer * 2 + 2]) {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 1];
    data[pointer * 2 + 1] = temp;
    pointer = pointer * 2 + 1;
   } else {
    int temp = data[pointer];
    data[pointer] = data[pointer * 2 + 2];
    data[pointer * 2 + 2] = temp;
    pointer = pointer * 2 + 2;
   }
  }
 }
}