[JavaScript] 힙 직접 구현 해보기

우선순위 큐 (Priority Queue)

우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다. 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
JavaScript에는 우선순위 큐 자료구조가 구현되어 있지 않다. 배열, 연결리스트, 힙 기반으로 우선순위 큐 자료구조를 구현 할 수 있으나, 배열이나 연결리스트 기반으로 구현 시 시간복잡도가 증가하기 때문에 보통 힙을 구현하고 힙을 기반으로 우선순위 큐를 구현한다.

구현 방법에 따른 시간 복잡도

배열 기반 우선순위 큐

삽입	삭제
$O(N)$	$O(1)$

연결리스트 기반 우선순위 큐

삽입	삭제
$O(N)$	$O(1)$

힙 기반 우선순위 큐

삽입	삭제
$O(LogN)$	$O(LogN)$

배열과 연결리스트는 데이터 삽입시 모든 인덱스를 탐색해야하는 경우 시간복잡도가 $O(N)$으로 성능이 좋지 않을 수 있다.

힙(Heap)

힙은 트리 기반의 자료구조이다. 규칙에 따라 크게 Max Heap과 Min Heap으로 나뉜다.

Max Heap (최대 힙)

• 루트 노드가 가장 큰 값을 가지며 우선적으로 제거된다.
• 부모 노드의 값 $\geq$ 자식 노드의 값

Min Heap (최소 힙)

• 루트 노드가 가장 작은 값을 가지며 우선적으로 제거된다.
• 자식 노드의 값 $\geq$ 부모 노드의 값

힙 자료구조는 완전이진트리로 구현한다. 완전이진트리는 각각의 부모노드는 두개의 자식 노드(Left, Right)만 가질 수 있고, 트리의 가장 아래 층을 제외하고는 상단의 모든 레벨이 채워져야 한다.

왼쪽 자식노드의 인덱스 : 부모 노드의 인덱스 x 2 + 1
오른쪽 자식노드의 인덱스 : 부모 노드의 인덱스 x 2 + 2
부모 노드의 인덱스 : (자식 노드의 인덱스 - 1) / 2 (소수점 버림)

1. 부모노드는 항상 자식 노드보다 값이 작아야(커야) 한다.
2. 한 레벨이 모두 채워져야 다음 레벨로 트리가 늘어날 수 있다.

이 두 가지 규칙을 지키는 자료구조를 힙(Heap)이라고 할 수 있다.

힙은 주로 최소(최대)값을 $O(1)$의 시간 복잡도로 얻어내기 위해서 사용된다.
배열이나 연결 리스트 같은 자료구조는 최소(최대)값을 얻기 위해 $O(N)$이 걸린다.
힙의 경우 최상위 노드에 항상 최소(최대)값이 담겨있기 때문에 최상위 노드의 조회 $O(1)$의 시간 복잡도만으로 최소(최대)값을 얻을 수 있다.

Min Heap 구현

1. 기본 구조

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

  // 인덱스 값 가져오기
  getLeftChildIndex(parentIndex) {
    return 2 * parentIndex + 1;
  }

  getRightChildIndex(parentIndex) {
    return 2 * parentIndex + 2;
  }

  getParentIndex(childIndex) {
    return Math.floor((childIndex - 1) / 2);
  } 
  
  // 자식/부모 노드 존재하는지 체크
  hasLeftChild(index) {
    return this.getLeftChildIndex(index) < this.heap.length;
  }

  hasRightChild(index) {
    return this.getRightChildIndex(index) < this.heap.length;
  } 
  
  hasParent(index) {
    return this.getParentIndex(index) >= 0;
  }
  
  // 자식/부모 노드 값 가져오기
  leftChild(index) {
    return this.heap[this.getLeftChildIndex(index)];
  }

  rightChild(index) {
    return this.heap[this.getRightChildIndex(index)];
  }

  parent(index) {
    return this.heap[this.getParentIndex(index)];
  }
  
  // 최상위 노드 peek
  peek() {
    if (this.heap.length === 0) {
      return null;
    }
    return this.heap[0];
  }
}

부모/자식 노드의 인덱스 값 반환, 존재 여부 체크, 노드 값 반환을 하는 메서드를 구현한다.
peek()은 항상 최상위 노드를 반환한다.

2. insert

class MinHeap {
  ...
  
  insert(data) {
  	this.heap.push(data);
    this.heapifyUp();
  }

  heapifyUp() {
	let index = this.heap.length - 1;
    while (this.hasParent(index) && this.parent(index) > this.heap[index]) {
      const parentIndex = this.getParentIndex(index);
      this.swap(parentIndex, index);
      index = parentIndex;
    }
    
  swap(index1, index2) {
    [this.heap[index1], this.heap[index2]] = [this.heap[index2], this.heap[index1]];
  	}
    
  }

insert()

• 최근에 삽입한 노드를 배열의 끝에 넣는다.
• Min Heap의 형태를 갖추도록 조정한다. (HeapifyUp)

heapifyup()
변수 index에 해당하는 노드가

• 부모 노드가 존재한다.
• 부모 노드의 값이 자식 노드의 값보다 크다

를 만족할 경우, 부모 인덱스와 자식 노드의 인덱스를 교환한다.
변수 index에 부모 노드의 인덱스 값을 할당하고 While 문이 반복된다.
이를 통해 최신 노드가 제 자리를 찾아 갈 수 있도록 아래에서 부터 위로 끌어 올린다.

3. remove

class MinHeap {
  ...
  
  remove() {
    if (this.heap.length === 0) {
      return null;
    }

    const root = this.heap[0]; // 최상위 노드
    const last = this.heap.pop(); // 끝에 있는 노드를 꺼내어 last에 할당

    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.heapifyDown();
    }

    return root;
  }
  
   heapifyDown() {
     let index = 0;
     while (this.hasLeftChild(index)) {
       let smallerChildIndex = this.getLeftChildIndex(index);
       if (this.hasRightChild(index) && this.rightChild(index) < this.leftChild(index)) {
		  smallerChildIndex = this.getRightChildIndex(index);
      }

      if (this.heap[index] < this.heap[smallerChildIndex]) {
		  break;
      } else {
          this.swap(index, smallerChildIndex);
      }

      index = smallerChildIndex;
     }
     
  	}
    
  }

insert()

• 변수 root와 last에 각각 최상위 노드와 제일 끝 노드를 할당
• 제일 끝 노드를 최상위 노드로 만든다.
• Min Heap의 형태를 갖추도록 조정한다. (HeapifyDown)

heapifyDown()
최상위 노드 ( insert()에서 최상위 노드가 제일 끝 노드)를 시작으로, 두 자식노드 중 값이 작은 노드를 찾아, 부모 노드와 비교하여 자식 노드의 값이 더 작을경우 그 둘의 인덱스 값을 교환한다. 변수 index에 자식 노드의 값을 할당하고 while 문이 반복된다.
이를 통해, 최근 자리가 바뀐 최상위 노드의 올바른 위치를 찾아 아래로 끌어 내린다.

실행 결과

	const heap = new MinHeap();
	heap.insert(2);
	heap.insert(8);
	heap.insert(4);
	heap.insert(6);
	
	console.log(heap.peek()); 	// 2
	console.log(heap.remove()); // 2
	console.log(heap.peek()); 	// 4
	console.log(heap.remove()); // 4

	heap.insert(2);
	connsole.log(heap.peek()) 	// 2

참조

• https://jun-choi-4928.medium.com/javascript%EB%A1%9C-heap-priority-queue-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0-8bc13bf095d9
• https://ji-musclecode.tistory.com/46
• https://velog.io/@qltkd5959/JS
• https://hokeydokey.tistory.com/72