ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 자료구조 힙(Heap), 힙 정렬(Heap Sort)
    Computer Science/Algorithm, Data Structure 2019.06.03 17:35

    출처: https://github.com/leonardomso/33-js-concepts(모든 자바스크립트 개발자가 알아야 하는 33가지 개념)

     

    해시 테이블에 이어서 Heap(힙)에 대해 알아보자.

     

    Heap(힙)은 max-heap(최대 힙), min-heap(최소 힙) 속성을 충족시키는

     

    트리 기반 데이터 구조이다.

     

    힙을 번역하면 명사로 더미, 쌓아 올린 것이다.

     

    최대힙(max heap)

     

    부모가 없는 상단에 있는 노드를 Root(루트) 노드라고 한다.

     

    최대 힙은 루트 노드가 자식들보다 커야 한다.

     

    최소힙(min heap)

     

    최소 힙은 최대 힙의 반대로 루트 노드가 자식들보다 작아야 한다.

     

    또한 왼쪽에서부터 들어가는 완전 트리 여야 한다.

     

    이 조건은 서브 트리에도 적용이 된다.

     

    고로 힙 정렬은 일차원 배열로 표현 가능하다.

     

    A[0..n]

     

    루트 노드 A[i = 0] 가정하면,

     

    A[i]의 부모 = A[(i-1)/2]

     

    A[i]의 왼쪽 자식 = A[2i+1]

     

    A[i]의 오른쪽 자식 = A[2i+2]

     

    출처: https://reactgo.com/javascript-heap-datastructure/

     

    max-heap(최대 힙) 구현을 해보자.

     

    class BinaryHeap {
      constructor() {
        this.heap = [30, 20, 10, 7, 9, 5]
      }
    
      insert(value) {
        this.heap.push(value)
        this.bubbleUp()
      }
      bubbleUp() {
        let index = this.heap.length - 1;
    
        while (index > 0) {
          let element = this.heap[index];
    
          let parentIndex = Math.floor((index - 1) / 2);
    
          let parent = this.heap[parentIndex];
    
          if (parent >= element) break;
          this.heap[index] = parent;
          this.heap[parentIndex] = element;
          index = parentIndex
        }
      }
    
      extractMax() {
        let max = this.heap[0]
        this.heap[0] = this.heap.pop()
        this.sinkDown(0)
        return max
      }
      sinkDown(index) {
        let left = 2 * index + 1,
            right = 2 * index + 2,
            largest = index;
        const length = this.heap.length
    
        if (left <= length && this.heap[left] > this.heap[largest]) {
          largest = left
        }
        if (right <= length && this.heap[right] > this.heap[largest]) {
          largest = right
        }
    
        if (largest !== index) {
          [this.heap[largest], this.heap[index]] = [this.heap[index], this.heap[largest]]
          this.sinkDown(largest)
        }
      }
    }
    
    const heap = new BinaryHeap();
    heap.insert(90);
    heap.insert(50);
    console.log(heap) // BinaryHeap { heap: [ 90, 50, 30, 20, 9, 5, 10, 7 ] }
    heap.extractMax() // 90

     

    insert(value) -> 값 추가하기

     

    배열에 들어온 값을 넣고 bubbleUp 메서드를 호출한다.

     

    bubble Up이라고 명칭을 지은 건 마치 끌어올리는 듯 느낌을 내기 위함 인 것 같다.

     

    현재 들어온 값의 index를 구하려면 전체 배열의 크기에서 1을 빼준다.

     

    반복문 while을 통해서 부모 트리를 구하고 값을 비교하여

     

    부모의 값이 자식의 값보다 크거나 같으면 반복문을 탈출한다.

     

    부모의 값이 자식의 값보다 작으면 바꿔 준다.(Swap)

     

    여기까지 한 것을 다시 반복한다. (최상단 루트 비교까지)

     

    extractMax() 최댓값 구하기

     

    상단 루트의 값이 최댓값 이므로 max 변수에 저장한다.

     

    pop() 메서드로 배열 마지막 값을 최상단 루트 노드로 올려 준다.

     

    sinkdown() 메서드 호출

     

    최상단 루트의 값과 왼쪽, 오른쪽 자식의 값과 비교를 하여

     

    가장 높은 값과 바꿔 준다.(Swap)

     

    다시 최대 힙을 구성할 때까지 재귀적 호출을 한다.

    댓글 12