[자료구조] heap

1. 부모 노드는 자식 노드보다 커야된다.

2. 그러기 위해서 트리구조 / 배열 구조를 이용할수 있는데 이번에는 배열 구조를 이용해서 구하는 방식에 대해서 공부함

3.배열의 맨 마지막에 push 한후 그 index 와 부모 index를 비교해서 swap 해 주면 완료 이때 while 문을 사용하기 때문에 break 문과 한계 를 명시해야된다.



class heap {
  constructor() {
    this.arr = [];
    this.length = 0;

  }
  add(val) {
    if (this.length == 0) {
      this.arr.push(val);
      this.length += 1;

    }
    else if (this.length > 0) {
      this.arr.push(val);
      var inex = this.arr.length - 1;
      while (inex > 0) {
        var check = Math.floor((inex - 1) / 2);

        if (this.arr[inex] > this.arr[check]) {
          var swap = 0;
          swap = this.arr[check];
          this.arr[check] = this.arr[inex];
          this.arr[inex] = swap;
          inex = check;

        }
        else if (this.arr[inex] < this.arr[check]) {
          break;

        }

      }


    }
    console.log(this.arr)

  }

}

const he = new heap();
he.add(14);
he.add(77);
he.add(88);
he.add(4);
he.add(100);
he.add(50);
he.add(78);


정리가 잘 된것을 볼수 있다.

좋은 웹페이지 즐겨찾기