[자료구조 / Javascript] Heap

1. Heap이란?

 - 최댓값 또는 최솟값을 빠르게 찾아내기 위해 고안된 완전 이진트리를 기반으로 하는 자료구조이다.

 - Heap은 이진트리라는 특성 덕분에 반 정렬상태를 유지한다. 

     - 부모 노드의 값이 자식 노드의 값보다 항상 크거나(Max heap) 작은(Min heap) 이진 트리를 말한다.

     - 즉, 값의 대소관계는 오로지 부모노드와 자식노드 간에만 성립하며, 특히 형제 사이에는 대소관계가 정해지지 않는다.

 - 힙에서는 가장 높은(혹은 가장 낮은) 값을 가지는 노드가 항상 Root 노드에 오게 되는 특징이 있으며, 이를 응용하면 우선 순위 큐와 자료형을 구현할 수 있다.

 

2. Heap의 종류

 - Max  heap

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

 - Min heap

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

https://www.geeksforgeeks.org/heap-data-structure/

 

3. Heap내 노드들의 위치

 - Javascript에서 힙은 배열을 기반으로 한다.

 - 힙에서의 부모 / 자식 노드는 아래와 같이 표현할 수 있다.

    - 부모 노드의 인덱스 = Math.floor(자식 노드의 인덱스 - 1) / 2

    - 왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 x 2 + 1

    - 오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 x 2 + 2

 

4.  복잡도

 - 삽입 : O(logn)

 - 삭제 : O(logn)

 - 정렬:  O(nlogn)

 

5. Heap의 생성 / 삽입 / 삭제 / 정렬

 - Heap 자료 구조의 동작 원리는 visualgo.net/ko/heap 를 통해 쉽게 시각적으로 파악할 수 있다.

 

6. Heap 구현

 Javascript로 구현한 Heap의 코드는 아래와 같다.

class Heap {
  constructor() {
    this.heap = []
  }
  isEmpty(){ return this.isEmpty() }
  peek(){ return this.heap[0] }
  getLeftChildIndex(parentIndex){ return parentIndex * 2 + 1 }
  getRightChildIndex(parentIndex){ return parentIndex * 2 + 2 }
  getParentIndex(childIndex){ return Math.floor((childIndex - 1) / 2) }
  isEmpty(){ return this.heap.length <= 0 }
  insert(key, value){
    this.heap.push({ key, value }) 
    this.heapifyUp() 
  }
  heapifyUp(){
    let index = this.heap.length - 1 
    const lastInsertedNode = this.heap[index]
    while (index > 0) {
      const parentIndex = this.getParentIndex(index)

      if (this.heap[parentIndex].key > lastInsertedNode.key) {
        this.heap[index] = this.heap[parentIndex]
        index = parentIndex
      } else break
    }
    this.heap[index] = lastInsertedNode
  }
  remove(){
    const count = this.heap.length
    const rootNode = this.heap[0]

    if (count <= 0) return undefined
    if (count === 1) this.heap = []
    else {
      this.heap[0] = this.heap.pop() 
      this.heapifyDown() 
    }
    return rootNode
  }
  heapifyDown(){
    let index = 0
    const count = this.heap.length
    const rootNode = this.heap[index]

    while (this.getLeftChildIndex(index) < count) {
      const leftChildIndex = this.getLeftChildIndex(index)
      const rightChildIndex = this.getRightChildIndex(index)

      const smallerChildIndex =
        rightChildIndex < count && this.heap[rightChildIndex].key < this.heap[leftChildIndex].key
          ? rightChildIndex
          : leftChildIndex

      if (this.heap[smallerChildIndex].key <= rootNode.key) {
        this.heap[index] = this.heap[smallerChildIndex]
        index = smallerChildIndex
      } else break
    }

    this.heap[index] = rootNode
  }
}

7. Priority Queue 구현

 Heap을 사용하면 우선순위 큐를 쉽게 구현할 수 있는데, 그 코드는 아래와 같다.

class PriorityQueue extends Heap {
  constructor() {
    super()
  }

  enqueue(priority, value){ this.insert(priority, value) }
  dequeue(){ return this.remove() }
}

8. Heap sort 구현

 마찬가지로 Heap 자료구조를 이미 구현했다면, Heap sort도 쉽게 구현할 수 있다.

function heap_sort(numbers){
  var h = new Heap()
  for(let number of numbers){
    h.insert(number, number)
  }

  var sortedNumbers = []
  while(!h.isEmpty()){
    sortedNumbers.push(h.remove().value)
  }

  return sortedNumbers
}

9. Min heap < -- > Max heap

만약 heap의 상태를 max에서 min으로 또는 min에서 max로 변경하고 싶다면 아래 함수를 이용하면 된다.

  convertMaxHeap() {
    const maxHeapify = (i) => { 
      let n = this.heap.length
      let left = 2*i + 1
      let right = 2*i + 2
      let largest = i
      if (left < n && this.heap[left].key > this.heap[i].key) 
          largest = left
      if (right < n && this.heap[right].key > this.heap[largest].key) 
          largest = right
      if (largest != i) { 
          let temp = this.heap[i]
          this.heap[i] = this.heap[largest]
          this.heap[largest] = temp
          this.maxHeapify(largest)
      }
    }
    let n = this.heap.length 
    for (let i = Math.round((n-2)/2); i >= 0; i--) 
      maxHeapify(i)
  }
  
  convertMinHeap() {
    const minHeapify = (i) => { 
      let n = this.heap.length
      let left = 2*i + 1
      let right = 2*i + 2
      let smallish = i
      if (left < n && this.heap[left].key < this.heap[i].key) 
          smallish = left
      if (right < n && this.heap[right].key < this.heap[smallish].key) 
          smallish = right
      if (smallish != i) { 
          let temp = this.heap[i]
          this.heap[i] = this.heap[smallish]
          this.heap[smallish] = temp
          this.minHeapify(smallish)
      }
    }
    let n = this.heap.length 
    for (let i = Math.round((n-2)/2); i >= 0; i--) 
      minHeapify(i)
  }