Algorithm | 자료구조 : 힙(Heap)

Heap ?

힙의 구조    출처  https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 힙(Heap)은 부모 노드와 자식 노드 간에는 키 값의 대소관계가 존재하는 완전 이진트리이다. 대소관계는 오로지 부모 노드와 자식 노드 간에만 성립하며 형제 사이에는 대소관계가 정해지지 않는다. 부모 노드의 값이 자식 노드의 값보다 크거나 같으면 최대 힙(Max Heap), 그 반대면 최소 힙(Min Heap)이다. 

* 이진트리(Binary Tree) : 한 노드가 최대 두 개의 자식노드를 가지는 트리

* 완전 이진트리(Complete Binary Tree) : 노드를 삽일할 때 왼쪽부터 차례대로 삽입하는 이진 트리이다.

 

 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었으며 우선순위 큐를 구현할 때 주로 사용된다.

* 우선순위 큐(Priority Queue) : 우선순위가 높은 데이터가 먼저 나오는 큐

 

Heap 구현 (in Java)

 힙을 저장하는 표준적인 자료구조는 배열이다. 힙에서의 부모 노드와 자식 노드는 항상 일정한 관계를 가지고 있으므로 배열의 인덱스를 활용하여 구현이 가능하다.

 

· 왼쪽 자식의 인덱스 = 부모의 인덱스 * 2

· 오른쪽 자식의 인덱스 = 부모의 인덱스 * 2 + 1

· 부모의 인덱스 = 자식의 인덱스 / 2

배열을 이용한 힙의 구현      출처  https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 배열을 이용하여 새로운 요소를 삽입하거나 삭제할 수 있는 최대 힙을 구현해보자.

 

Element 삽입

 

 새로운 요소를 힙에 삽입하는 과정은 다음과 같다.

 

1. 새로운 노드를 힙의 가장 마지막 노드에 이어서 삽입한다.

2. 새로운 노드와 부모 노드와 비교하여 힙의 성질을 만족시킬 수 있을 때까지 부모 노드와 교환한다.

 

힙의 삽입       출처  https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

Element 삭제

 

 힙에서의 삭제 연산은 루트 노드(최댓값 혹은 최솟값)을 삭제하는 것이다. 삭제 연산 과정은 다음과 같다.

 

1. 루트 노드를 삭제한다.

2. 힙의 가장 마지막 노드를 루트 노드로 삽입시킨다.

3. 삽입된 노드를 자식 노드와 비교하며 힙의 성질을 만족시킬 수 있을 때까지 자식노드와 교환한다.

 

힙의 삭제     출처  https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

 

import java.util.ArrayList;

/**
 * MyMaxHeap
 */
public class MyMaxHeap {
  private ArrayList<Integer> heap;

  // Constructor
  public MyMaxHeap() {
    heap = new ArrayList<>();
    heap.add(-1); // 인덱스를 1부터 시작하기 위함.
  }

  // 위치 교환 메서드
  private void swap(int i1, int i2) {
    int temp = heap.get(i1);
    heap.set(i1, heap.get(i2));
    heap.set(i2, temp);
  }

  public void insert(int node) {
    heap.add(node);
    int p = heap.size() - 1;  // 노드의 현재 위치를 표시할 포인터

    // 노드의 위치가 최상위가 되거나
    // 부모 노드의 값이 더 클 때 까지 교환작업 진행
    while(p > 1 && heap.get(p/2) < heap.get(p)) {
      swap(p/2, p); // 교환
      p = p / 2;  // 포인터 이동
    }
  }

  public int delete() {
    if(heap.size() == 1) {  // 힙이 비어있을 경우
      return 0;
    }

    int deletedNode = heap.get(1);
    heap.set(1, heap.get(heap.size()-1)); // 루트 노드의 값을 마지막 노드의 값으로 변경
    heap.remove(heap.size()-1); // 마지막 노드 삭제
    int p = 1;  // 노드의 현재 위치

    // 자식노드가 있을 때까지 반복
    while(p * 2 < heap.size()) {
      // 오른쪽 자식이 없을 경우를 생각해주어야함... 자꾸 p*2+1 인덱스 예외뜸...
      int max_p = p * 2;  // 왼쪽 오른쪽 중 더 큰 값을 가진 노드의 인덱스를 저장할 변수
      if(p * 2 + 1 < heap.size()) { // 오른쪽 자식이 있을 경우
        // 자식 노드 중 더 큰 노드와 교환한다.
        if(heap.get(p*2) < heap.get(p*2+1)) {
          max_p = p*2 + 1;
        }
      }

      if(heap.get(p) > heap.get(max_p)) { // 부모가 자식보다 값이 더 크다면 반복문 탈출
        break;
      }else {
        swap(p, max_p); // 아니라면 값 교환
        p = max_p;  // 포인터 변경
      }
    }

    return deletedNode;
    
  }
}

 

---

Reference

 

· 위키백과 힙 - https://ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0)

· 힙(Heap)이란 - https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

· Binary Heaps - https://www.youtube.com/watch?v=jfwjyJvbbBI

·힙 구현하기 - https://muckycode.blogspot.com/2015/01/heap_11.html