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);

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

REMOVING !!

array 마지막 수 를 맨 위로 보낸후 그 자리가 맞는지 확인하는 함수를 구현해보자

index2+1 index2+2 중에서 큰수 밑으로 가자

오류가 계속 나서 왜지? 생각해보니까 만약 자식 노드가 없는 자리이면 return 으로 바로 반환해야된다.

  slide_down() {


    var hey = this.arr.shift();
    console.log(hey)
    var list = this.arr[this.arr.length - 1];
    this.arr.unshift(list);
    this.arr.pop();
    var index = 0;

    while (true) {
      if (index * 2 + 1 > this.arr.length - 1) {
        break;
      }
      if (this.arr[index] < this.arr[index * 2 + 1] || this.arr[index] < this.arr[index * 2 + 2]) {
        if (this.arr[index * 2 + 1] > this.arr[index * 2 + 2]) {
          var hee = 0;
          hee = this.arr[index * 2 + 1];
          this.arr[index * 2 + 1] = this.arr[index];
          this.arr[index] = hee;

          index = index * 2 + 1;

        }
        else if (this.arr[index * 2 + 1] < this.arr[index * 2 + 2] || this.arr[index * 2 + 1] < this.arr[index * 2 + 1]) {
          var heev = 0;
          heev = this.arr[index * 2 + 2];
          this.arr[index * 2 + 2] = this.arr[index];
          this.arr[index] = heev;

          index = index * 2 + 2;

        }


      }
      else if (this.arr[index] > this.arr[index * 2 + 1] || this.arr[index] > this.arr[index * 2 + 2]) {
        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);
he.slide_down();
he.slide_down()
he.slide_down()
he.slide_down()

제대로 되는 것을 볼수 있다.