본문 바로가기
Computer Science/Algorithm, Data Structure

자바스크립트 자료구조 힙(Heap), 힙 정렬(Heap Sort)

by Write and Remember 2019. 6. 3.

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

 

2019/05/30 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 해시 테이블(Hash Table)

 

자바스크립트 자료구조 해시 테이블(Hash Table)

2019/05/26 - [Computer Science/Algorithm, Data Structure] - 자바스크립트 자료구조 연결 리스트(Linked List) 자바스크립트 자료구조 연결 리스트(Linked List) 모든 자바스크립트 개발자가 알아야 하는 33가..

jeongw00.tistory.com

 

해시 테이블에 이어서 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)

 

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

댓글8