[자료구조] 힙(heap), 우선순위큐

힙(힙트리)

• 힙은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 이진트리
• 우선순위 큐를 만들 때 사용됨
• Max힙: 부모노드의 값이 자식노드보다 큰 힙
• Min힙: 자식노드의 값이 부모노드보다 큰 힙

 

이진힙

• 완전 이진트리의 일종

완전이진트리

녹색 화살표방향으로 노드를 채워나가는 트리가 완전이진트리
x 표시 되어 있는 트리는 완전이진x

• 이진힙은 가능한 모든노드(left,right)를 채우고 자식노드로 내려간다. 그렇기 때문에 이진트리에 비해 공간 효율적

 

배열과 완전이진트리

완전 이진트리는 배열의 형태로 나타낼 수 있다.

• 위와같은 트리를 배열로 => [A,B,C,D,E]

배열로 나타낸 완전이진트리에서는 아래와 같은 공식이 성립한다.

• (부모인덱스 * 2) + 1 = 왼쪽자식인덱스
• (부모인덱스 * 2) + 2 = 오른쪽자식인덱스

 

공식이 성립하는 수학적 이유

https://cs.stackexchange.com/questions/87154/why-does-the-formula-2n-1-find-the-child-node-in-a-binary-heap

 

공식이 성립하는 직관적 이유

• 1번 부터 n번까지의 노드가있다고 가정(1부터 인덱스 시작)
• n번 노드의 자식노드를 추가할 때 n 이전의 모든 노드(1 ~ n-1)는 둘의 자식을 가지고있다.
• n-1번 까지의 모든 자식노드의 갯수 + 루트노드 = (n-1)*2 + 1 = 2n-1
• n번 노드의 첫번째, 두번째 자식은 각각 2n, 2n+1 번째임
• 0번 인덱스부터 시작한다면 2n+1, 2n+2

 

배열과 그 성질을 이용한 최대이진힙 구현하기

insert 메소드

instance.insert(99)

class MaxBinaryHeap {
  constructor() {
    this.values = [];
  }
  #swapValues(idx1, idx2) {
    [this.values[idx1], this.values[idx2]] = [this.values[idx2], this.values[idx1]];
  }
  #bubbleUp() {
    let newItemIdx = this.values.length - 1;
    while (1) {
      let parentIdx = Math.floor((newItemIdx - 1) / 2);
      if (this.values[newItemIdx] <= this.values[parentIdx]) break;
      this.#swapValues(parentIdx, newItemIdx);
      newItemIdx = parentIdx;
    }
  }
  insert(val) {
    this.values.push(val);
    if (this.values.length > 1) this.#bubbleUp();
    return this.values;
  }

}

 

extractMax 메소드

• root를 추출하는 메소드

instance.extractMax()

class MaxBinaryHeap {
    // 생성자
    // 메소드 ...
  #swapValues(idx1, idx2) {
    [this.values[idx1], this.values[idx2]] = [this.values[idx2], this.values[idx1]];
  }
  #sinkDown(currentIdx = 0) {
    while (1) {
      const [firstChildIdx, secondChildIdx] = [currentIdx * 2 + 1, currentIdx * 2 + 2];
      const [firstChild, secondChild] = [this.values[firstChildIdx], this.values[secondChildIdx]];
      const targetValue = this.values[currentIdx];
      if (firstChild === undefined) break;
      if (secondChild === undefined) {
        if (targetValue >= firstChild) return;
        this.#swapValues(firstChildIdx, currentIdx);
        currentIdx = firstChildIdx;
        continue;
      }
      const maxChild = Math.max(firstChild, secondChild);
      if (maxChild <= targetValue) return;
      const childObj = { [firstChild]: firstChildIdx, [secondChild]: secondChildIdx };
      const maxChildIdx = childObj[maxChild];
      this.#swapValues(currentIdx, maxChildIdx);
      currentIdx = maxChildIdx;
    }
  }
  extractMax() {
    this.#swapValues(0, this.values.length - 1);
    const max = this.values.pop();
    this.#sinkDown();
    return max;
  }
  // 메소드..
}

 

Big O

• 삽입, 제거 O(logN)
• 검색 O(N)

 

 

우선순위큐

• 우선순위 큐는 일반적인 우선순위에 따른 순서를 가지고있는 큐이다.
• 배열, 리스트. 힙 등으로 구현가능
• 위에서 구현한 이진 힙트리의 각 노드 값이 우선순위라고한다면 위의 이진힙을 곧 우선순위 큐라고도 볼 수 있다.
• 다만 같은 우선순위를 가진 값에 대한 처리가 추가되어야한다.(삽입된 시간 등 을 체크해서 구현가능)
• priority 프로퍼티의 값이 클수록 우선순위가 높은것이라고 한다면 위처럼 최대힙을 반대라면 최소힙을 이용하면된다.