Javascript 자료구조 07 : Heap

Heap(힙)

힙은 '최대값 혹은 최소값'을 빠르게 찾기 위한 완전 이진 트리
(이전 글에서 다뤘던 이진 탐색 트리는 '탐색'을 빠르게 하기 위한 구조)

• 완전 이진 트리 : node를 삽입할 때 최하단 왼쪽 node부터 차례로 삽입하는 트리. 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있고, 마지막 레벨의 node는 왼쪽부터 채워져있는 구조.

Min Heap(최소 힙)

1. 완전 이진 트리
2. 각 node의 값은 자식 node가 가진 값보다 작거나 같다.
   (root의 값이 가장 작다.)

Max Heap(최대 힙)

1. 완전 이진 트리
2. 각 node의 값은 자식 node가 가진 값보다 크거나 같다.
   (root의 값이 가장 크다.)

insert(데이터 삽입)

1. 완전 이진 트리의 조건에 따라서 data를 삽입한다.
2. swap : 새로 삽입한 값과 그 부모 node를 비교하여 위치를 맞바꾼다.

ex) max heap의 경우,
    if (new Node > parent Node) swap
    조건에 맞지 않을 때까지, root까지 반복.

pop(데이터 삭제)

Heap은 최대 값 혹은 최소 값을 탐색하기 위해 고안된 자료구조로, 최대 값 혹은 최소 값만을 삭제한다. 이는 root Node를 삭제하는 것과 같다.

1. 마지막으로 삽입된 Node를 root와 swap
2. 마지막 자리로 간 root Node의 값을 삭제(pop)
3. root Node와 child Node들을 비교해가면서 child Node가 더 크면 swap
   분기 : 1. No Child, 2. One Child(left), 3. Two Children

Heap(힙) & Array(배열)

• 배열로 힙을 구현할 수 있음
• 배열 index 0은 비워두고, index 1부터 활용.
• child node index // 2 = parent node index (몫)
• parent node index * 2 = left child node
• parent node index * 2 + 1 = right child node

Max Heap(최대 힙) 구현

class Heap {
  constructor() {
    // index 0에 null을 입력
    this.heap = [null];    
  }
  insert(data) {
    this.heap.push(data);
    let current = this.heap.length - 1;
    if (current <= 1) return;
    let parent = parseInt(current / 2); // 2로 나눈 몫을 구하면 parent index
    while (this.heap[parent] < this.heap[current]) {
      this.swap(parent, current); // parent와 current의 값을 swap
      current = parent; // current에 parent를 할당
      if (current === 1) break; // current 값이 1이면 최상위로 올라온 것이므로 break;
      parent = parseInt(current / 2); // 2로 나눈 몫을 구하면 현재 current의 parent index
    }
  }
  swap(a, b) {
    [this.heap[a], this.heap[b]] = [this.heap[b], this.heap[a]];
  }
  pop() {
    // index 1과 마지막으로 삽입된 index의 값을 swap
    this.swap(1, this.heap.length - 1);
    // 배열 마지막에 위치한 최대값을 pop
    let maxVal = this.heap.pop();

    let current = 1;

    // 비교해서 큰 값을 위로 올려줌.
    // 분기 : 1. No Child, 2. One Child(left), 3. Two Children
    while (current <= this.heap.length) {
      let left = current * 2;
      let right = current * 2 + 1;
      // 1. No Child
      if (left > this.heap.length) {
        break;
      } // 2. One Child(left) - 완전 이진 트리 조건에 따라 One Child이면 left만 존재함.
      else if (right > this.heap.length) {
        // right 값이 존재하지 않을 때
        if (this.heap[current] < this.heap[left]) {
          // current값 보다 left 값이 더 크면
          this.swap(current, left); // current와 left 값을 swap하여 더 큰 값을 위로 올려줌.
          current = left;
        }
      }
      // 3. Two Children(left, right)
      else {
        if (this.heap[left] > this.heap[right]) {
          // right보다 left가 더 클 경우
          // current와 left를 비교 후 swap
          if (this.heap[current] < this.heap[left]) {
            this.swap(current, left);
            current = left;
          }
        } else {
          // left보다 right이 더 클 경우
          // current와 right를 비교 후 swap
          if (this.heap[current] < this.heap[right]) {
            this.swap(current, right);
            current = right;
          }
        }
      }
    }
    return maxVal;
  }
}

테스트 코드

const heap = new Heap();
heap.insert(1);
heap.insert(2);
heap.insert(10);
heap.insert(6);
heap.insert(5);
heap.insert(9);
heap.insert(11);
heap.insert(3);
console.log(heap.pop()); // 11
console.log(heap); // [null, 10, 6, 9, 3, 5, 2, 1]

• 2020.04.13 최초 작성
• 2020.04.15 Heap pop(삭제) 코드 추가

댓글 환영 질문 환영
by.protect-me