자료구조 / 힙 Heap

힙 Heap

 

정의

힙은 완전 이진 트리 자료구조 이다.

힙에서는 항상 루트 노드를 제거한다.

 

종류

최소힙 (min heap)

• 루트 노드가 가장 작은 값을 가진다.
• 가장 작은 데이터가 우선적으로 제거된다.

 

최대힙 (max heap)

• 루트 노드가 가장 큰 값을 갖는다.
• 값이 가장 큰 데이터가 우선적으로 제거된다.

 

완전 이진 트리란?

루트 노드 부터 시작하며 왼쪽 자식 노드,

오른쪽 자식 노드 순서로 데이터가

차례대로 삽입되는 트리를 의미한다.

 

 

 

 

 

 

 

 

 

 

힙에 새로운 원소가 삽입될 때

새로운 원소가 삽입되었을 때 O(log N)의

시간 복잡도로 힙 성질을 유지할 수 있다.

 

삽입시에 부모 노드와 크기를 비교하여 자리를 바꾼다.

(최소힙은 부모노드 보다 작으면 up, 최대힙은 크면 up)

비교결과가 false 혹은 노드 도착시 끝

➡➡이것을 bubble up이라 한다

 

 

 

 

 

 

 

힙에서 원소(값) 제거하기(가져오기)

원소가 제거되었을 때 O(log N)의 시간 복잡도로 힙성질을 유지하도록 할 수 있다.

제거시에 가장 작은(or 큰)수를 제거 후 그 자리에 마지막 수를 배치한다.

그리고 자식 노드와 비교 후 가장 작은 수와 위치를 바꾸는 동작을 마지막 까지 진행한다.

(최대 O(log N) 시간이 걸린다.)  ➡➡ bubble down

 

아래는 최소 힙을 Javascript로 구현한 코드이다.

class MinHeap {
  constructor() {
    this.heap = [];
  }

  push(value) {
    this.heap.push(value);
    this.heapifyUp();
  }

  pop() {
    if (this.isEmpty()) return null;

    const root = this.heap[0];
    const lastNode = this.heap.pop();

    if (!this.isEmpty()) {
      this.heap[0] = lastNode;
      this.heapifyDown();
    }

    return root;
  }

  isEmpty() {
    return this.heap.length === 0;
  }

  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }

  heapifyUp() {
    let index = this.heap.length - 1;
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[parentIndex] <= this.heap[index]) break;
      this.swap(index, parentIndex);
      index = parentIndex;
    }
  }

  heapifyDown() {
    let index = 0;

    while (true) {
      let smallest = index;
      const leftChildIndex = 2 * index + 1;
      const rightChildIndex = 2 * index + 2;

      if ( this.heap[leftChildIndex] && this.heap[leftChildIndex] < this.heap[smallest] ) {
        smallest = leftChildIndex;
      }

      if ( this.heap[rightChildIndex] && this.heap[rightChildIndex] < this.heap[smallest] ) {
        smallest = rightChildIndex;
      }
      // 좌우 자식 모두 없는 경우
      if (smallest === index) break;

      this.swap(index, smallest);
      index = smallest;
    }
  }
}

 

최대힙의 경우는 조건을 반대로 해주면 된다.