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

    • 프로필사진

      선배님한테서 배우고십군요..
      화이팅

      2019.06.06 18:48 신고
    • 프로필사진

      예...그래요.
      톱 프로그래머이십니다.

      2019.06.06 18:57 신고
      • 프로필사진

        헉🤔 아닙니다.. 주니어에요ㅜㅜ 제가 아는 한 최대한 알려드릴게요

        2019.06.06 19:03 신고
    • 프로필사진

      고맙습니다. 웹을 배여려고 하는데요 무엇을 어떻게 해야 겠는 지 모르겠네요.
      JeongWoo님한테서 배우고픈데 어떻게 하면 좋을지...
      시키는데로 하죠.

      2019.06.06 19:07 신고
      • 프로필사진

        앗..저는 학부생이여서... 완전 처음이시고 입문자이시면 생활코딩: https://www.opentutorials.org/course/1
        접속하셔서 한번 보시면 웹 프로그래밍 입문하는데 도움 많이 되실거에요. 무료이고 강사님 잘 가르치세요

        2019.06.06 19:14 신고
    • 프로필사진

      정말 고맙네요. ㅠㅠ
      계속 연계하면...
      김영목 19세 여자 입니다.

      2019.06.06 21:12 신고
    • 프로필사진

      해답을 안하시는가요/

      2019.06.07 20:03 신고
    • 프로필사진

      안녕하세요! 웹디자이너 재직 중에 있습니다.
      매번 자바 공부한다고 해놓고 안하다가 이렇게 자극받고 갑니다 ㅠㅅㅠ
      자주 이야기 나눠요!

      2019.06.09 22:17 신고
      • 프로필사진

        반갑습니다!
        전 디자인쪽은 아니지만 유사 계열이네요.혹시 디자인 툴 어떤거 쓰시나요? 현업에서 Framer(프레이머) 사용하시나요?

        2019.06.09 22:49 신고
    • 프로필사진

      음 저는 디자인툴은 XD나 포토샵이네요. 어도비 계열을 주로 씁니다. 스케치도 가끔 쓰긴합니다.
      프레이머 좋다고 듣긴했는데 제 주변은 디자이너마다 프로그램 편차가 큰편이라ㅎㅎㅎ
      이것저것 공부하고 있습니다.

      2019.06.09 23:08 신고
Posted by JeongWoo