자료구조 06 힙 | JS

힙 | Heap

• 힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조
• A가 B의 부모노드(parent node) 이면, A의 키(key)값과 B의 키값 사이에는 대소관계가 성립한다.
• 대부분의 경우 자식노드의 갯수가 최대 2개인 이진 힙(binary heap)을 사용한다.
• 힙에서는 가장 높은(혹은 가장 낮은) 우선순위를 가지는 노드가 항상 뿌리노드에 오게 되는 특징이 있으며, 이를 응용하면 우선순위 큐와 같은 추상적 자료형을 구현할 수 있음

  정 이진 트리 vs 완전 이진 트리
  알고리즘 06 정렬 | 힙소트 | JS

최대힙 | Max Heap

• 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
  

최소힙 | Min Heap

• 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
  

최대 힙 구현

export default class Heap {
  constructor() {
    if (new.target === Heap) {
      throw new TypeError('Cannot construct Heap instance directly');
    }
    // 힙을 배열로 표현함
    this.heapContainer = [];
  }

  // 왼쪽 자식의 인덱스 = 부모의 인덱스 *2 + 1
  getLeftChildIndex(parentIndex) {
    return (2 * parentIndex) + 1;
  }
  // 오른쪽 자식의 인덱스 = 부모의 인덱스 *2 + 2
  getRightChildIndex(parentIndex) {
    return (2 * parentIndex) + 2;
  }
  // 부모의 인덱스 = ((자식의 인덱스 -1) / 2 ))의 내림값
  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  }

  hasParent(childIndex) {
    return this.getParentIndex(childIndex) >= 0;
  }
  hasLeftChild(parentIndex) {
    return this.getLeftChildIndex(parentIndex) < this.heapContainer.length;
  }
  hasRightChild(parentIndex) {
    return this.getRightChildIndex(parentIndex) < this.heapContainer.length;
  }

  leftChild(parentIndex) {
    return this.heapContainer[this.getLeftChildIndex(parentIndex)];
  }
  rightChild(parentIndex) {
    return this.heapContainer[this.getRightChildIndex(parentIndex)];
  }
  parent(childIndex) {
    return this.heapContainer[this.getParentIndex(childIndex)];
  }

  swap(indexOne, indexTwo) {
    const tmp = this.heapContainer[indexTwo];
    this.heapContainer[indexTwo] = this.heapContainer[indexOne];
    this.heapContainer[indexOne] = tmp;
  }

  peek() {
    if (this.heapContainer.length === 0) {
      return null;
    }
    return this.heapContainer[0];
  }

  poll() {
    if (this.heapContainer.length === 0) {
      return null;
    }

    if (this.heapContainer.length === 1) {
      return this.heapContainer.pop();
    }

    const item = this.heapContainer[0];

    // 마지막 요소를 끝에서 맨 위로 올림
    this.heapContainer[0] = this.heapContainer.pop();
    this.heapifyDown();

    return item;
  }

  add(item) {
    this.heapContainer.push(item);
    this.heapifyUp();
    return this;
  }

  remove(item) {
    // 삭제해야할 아이템의 갯수를 파악
    const numberOfItemsToRemove = this.find(item).length;

    for (let iteration = 0; iteration < numberOfItemsToRemove; iteration += 1) {
      // heapify 프로세스 후 인덱스가 변경되기 때문에
      // 삭제 후 매번 삭제할 요소의 인덱스를 찾아야함
      const indexToRemove = this.find(item).pop();

      // 마지막 요소를 삭제해야할 경우 heapify가 필요하지 않음
      if (indexToRemove === (this.heapContainer.length - 1)) {
        this.heapContainer.pop();
      } else {
        // Move last element in heap to the vacant (removed) position.
        // 마지막 요소를 삭제하는 것이 아닌 경우
        // 삭제하려는 요소의 자리에 마지막 요소의 값을 할당함
        this.heapContainer[indexToRemove] = this.heapContainer.pop();
        
        // 부모 요소를 찾음
        const parentItem = this.parent(indexToRemove);

        // Max heap의 경우
        // 부모 요소가 없거나 부모 요소가 현재 요소값보다 크면 heapify down
        // 그 외의 경우 heapify up
        if (
          this.hasLeftChild(indexToRemove)
          && (
            !parentItem
            || this.pairIsInCorrectOrder(parentItem, this.heapContainer[indexToRemove])
          )
        ) {
          this.heapifyDown(indexToRemove);
        } else {
          this.heapifyUp(indexToRemove);
        }
      }
    }

    return this;
  }

  // 인자와 같은 값을 가진 index를 찾아 배열로 반환함
  find(item) {
    const foundItemIndices = [];

    for (let itemIndex = 0; itemIndex < this.heapContainer.length; itemIndex += 1) {
      if (item === this.heapContainer[itemIndex]) {
        foundItemIndices.push(itemIndex);
      }
    }

    return foundItemIndices;
  }

  isEmpty() {
    return !this.heapContainer.length;
  }

  toString() {
    return this.heapContainer.toString();
  }

  heapifyUp(customStartIndex) {
    // 힙 컨테이너의 마지막 요소를 
    // 상위 요소에 대해 올바른 순서가 될 때까지 위로 올림    
    let currentIndex = customStartIndex || this.heapContainer.length - 1;

    // 부모 요소가 존재하고
    // && 부모 요소의 값과 현재 값을 비교해서 바꿔야 하는 상황이면 Swap
    // Swap을 했을 경우 현재 인덱스를 부모 인덱스로 업데이트
    while (
      this.hasParent(currentIndex)
      && !this.pairIsInCorrectOrder(
        this.parent(currentIndex), this.heapContainer[currentIndex]
      )
    ) {
      this.swap(currentIndex, this.getParentIndex(currentIndex));
      currentIndex = this.getParentIndex(currentIndex);
    }
  }

  heapifyDown(customStartIndex = 0) {
    // head부터 시작해서 부모 요소와 자식 요소를 비교 후
    // 올바른 순서가 될 때까지 아래로 내림
    let currentIndex = customStartIndex;
    let nextIndex = null;

    while (this.hasLeftChild(currentIndex)) {
      if (
        this.hasRightChild(currentIndex)
        && this.pairIsInCorrectOrder(
          this.rightChild(currentIndex), this.leftChild(currentIndex)
        )
      ) {
        // Max heap의 경우
        // 왼쪽 자식과 오른쪽 자식 모두 있고
        // 오른쪽 자식이 왼쪽 자식보다 클 경우 
        // 다음 인덱스는 오른쪽 자식으로 설정
        nextIndex = this.getRightChildIndex(currentIndex);
      } else {
        // 왼쪽 자식이 있는 상황에서
        // 오른쪽 자식이 없거나
        // 오른쪽 자식이 있어도, 오른쪽 자식이 왼쪽 자식보다 작거나 같을 경우
        // 다음 인덱스는 왼쪽 자식으로 설정
        nextIndex = this.getLeftChildIndex(currentIndex);
      }

      // Max heap의 경우
      // 현재 인덱스의 값이 다음 인덱스의 값보다 클 경우 => break
      if (this.pairIsInCorrectOrder(
        this.heapContainer[currentIndex],
        this.heapContainer[nextIndex],
      )) {
        break;
      }

      // Max heap의 경우
      // 현재 인덱스의 값이 다음 인덱스의 값보다 작거나 같을 경우 => swap
      this.swap(currentIndex, nextIndex);
      currentIndex = nextIndex;
    }
  }

  pairIsInCorrectOrder(firstElement, secondElement) {
    // Max Heap일 경우
    // 첫번째 인자가 두번째 인자보다 작거나 같아야함.
    // 그 반대의 경우 incorrect = true
    return firstElement > secondElement

    // Min Heap일 경우
    // 첫번째 인자가 두번째 인자보다 크거나 같아야함.
    // 그 반대의 경우 incorrect = true
    // return firstElement < secondElement
  }
}

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb

Photo by Alain Pham on Unsplash