[알고리즘] Heap

Heap은 최소 노드 또는 최대 노드를 찾는 알고리즘이다.
트리구조를 가지기 때문에 노드가 있고, 부모노드와 자식노드의 연결구조와 비교를 통해 최대 힙, 최소 힙 구할 수 있다.

Heap을 구성하기 위한 조건

1. 완전이진트리
2. 최대 힙일때는 부모노드 > 자식노드, 최소 힙은 부모노드 < 자식노드 이어야한다.

삽입 연산

heap에서 삽입연산을 실행할 때 주의해야 할 점은 노드의 위계가 변경되어서는 안된다.
새로운 노드를 추가한다면 마지막 노드에 임시로 저장 후 자신의 부모 노드와 비교하며 새로운 노드의 위치를 찾아가야한다.

아래 코드를 통해 확인 가능하다.

  exchange(a, b) {
    [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
  }

  insert(data){ 
    this.heap.push(data); // 빈 배열 끝에 값을 넣는다. (노드 가장 마지막에 새 노드를 추가)
    let curIndex = this.heap.length - 1; // 배열의 가장 마지막 index가 추가된 값의 index (마지막 노드의 index) 
    let parIndex = Math.floor(curIndex / 2); // 추가된 인덱스 값의 부모 인덱스가 되는 값 (추가된 노드의 부모 노드)

    while(curIndex > 1 && this.heap[parIndex] > this.heap[curIndex] ){ // curIndex가 1 이상이어야 부모노드가 있는 상태이고, 부모노드가 현재노드보다 클 때 해당 반복문이 실행된다.
      this.exchange(parIndex, curIndex); // 구조분해 할당을 통해 추가된 노드를 부모 노드와 변경해준다.(swap)

      curIndex = parIndex; // 현재노드를 부모노드와 바꿨기 때문에 바뀐 부모노드도 그 위의 부모노드와 비교해 값을 변경해줘야한다.
      parIndex = Math.floor(curIndex / 2); // 부모노드의 index값을 지정
    }
  }

삭제 연산

삭제 연산은 가장 작은 노드를 찾는 최소 힙이나 가장 큰 노드를 찾는 최대 힙 둘 다 최상위 노드(루트노드)가 그 값이 된다.
최상위 노드를 삭제하고 자식 노드를 비교해 최상위 노드로 위치를 옮겨줘야한다.
방법은 가장 마지막에 있는 노드를 최상위 노드로 옮겨 그 자식 노드들과 비교하며 위치를 조정한다.

아래 코드로 확인 가능하다.

delete() {
    const min = this.heap[1]; // 최상위 노드를 return
    if(this.heap.length <= 2) this.heap = [ null ];
    else this.heap[1] = this.heap.pop();
  // if-else 구문은 해당 리스트의 사이즈를 확인해 최상위 노드 이외의 노드가 없다면 null처리를 해주기 위해 필요하다.

    let curIndex = 1; // 현재 노드의 index
    let leftIndex = curIndex * 2; // 왼쪽 자식의 index
    let rightIndex = curIndex * 2 + 1; // 오른쪽 자식의 index


    if(!this.heap[leftIndex]) return min  // heap은 완전이진트리 구조가 필수조건이기 때문에 왼쪽 자식이 없다면 오른쪽 자식도 없다. 그래서 바로 min 최소노드를 return 해줄 수 있다.
    if((!this.heap[rightIndex])) { // 오른쪽 노드만 없다면 왼쪽 노드와 현재 노드를 비교해 exchange해준다.
      if(this.heap[leftIndex] < this.heap[curIndex]) {
        this.exchange(curIndex, leftIndex)
      }
      return min // exchange가 끝난 후 가장 노드를 Return 해준다.
    }

    while(this.heap[leftIndex] < this.heap[curIndex] || this.heap[rightIndex] < this.heap[curIndex]) { // 왼쪽 자식과 오른쪽 자식 둘 중 하나라도 현재 노드보다 작은 노드가 있다면 반복문을 실행한다.
      let minIndex = leftIndex < rightIndex ? leftIndex : rightIndex; // 왼쪽과 오른쪽 노드 중 더 작은 노드의 index값을 찾는다.
      this.exchange(curIndex, minIndex) // 둘 중 더 작은 노드의 index와 현재 노드의 index를 비교해 exchange를 해준다.

      curIndex = minIndex; // 변경된 노드의 자식노드와의 비교를 위해 현재 노드를 자식 노드 중 가장 작은 노드의 index로 변경해준다.
      leftIndex = curIndex * 2; // 변경된 노드의 왼쪽 노드의 index
      rightIndex = curIndex * 2 + 1; // 변경된 노드의 오른쪽 index
    }

    return min // 처음 구했던 최상위 노드(루트 노드)를 리턴한다.
  }
}

Heap 코드

class minHeap {
  constructor(){
    this.heap = [null];
  }

  size(){
    return this.heap.length - 1;
  }


  exchange(a, b) {
    [ this.heap[a], this.heap[b] ] = [ this.heap[b], this.heap[a] ];
  }

  insert(data){ 
    this.heap.push(data); // 빈 배열 끝에 값을 넣는다. (노드 가장 마지막에 새 노드를 추가)
    let curIndex = this.heap.length - 1; // 배열의 가장 마지막 index가 추가된 값의 index (마지막 노드의 index) 
    let parIndex = Math.floor(curIndex / 2); // 추가된 인덱스 값의 부모 인덱스가 되는 값 (추가된 노드의 부모 노드)

    while(curIndex > 1 && this.heap[parIndex] > this.heap[curIndex] ){ // curIndex가 1 이상이어야 부모노드가 있는 상태이고, 부모노드가 현재노드보다 클 때 해당 반복문이 실행된다.
      this.exchange(parIndex, curIndex); // 구조분해 할당을 통해 추가된 노드를 부모 노드와 변경해준다.(swap)

      curIndex = parIndex; // 현재노드를 부모노드와 바꿨기 때문에 바뀐 부모노드도 그 위의 부모노드와 비교해 값을 변경해줘야한다.
      parIndex = Math.floor(curIndex / 2); // 부모노드의 index값을 지정
    }
  }

  delete() {
    const min = this.heap[1];
    if(this.heap.length <= 2) this.heap = [ null ];
    else this.heap[1] = this.heap.pop();

    let curIndex = 1;
    let leftIndex = curIndex * 2;
    let rightIndex = curIndex * 2 + 1;


    if(!this.heap[leftIndex]) return min  
    if((!this.heap[rightIndex])) {
      if(this.heap[leftIndex] < this.heap[curIndex]) {
        this.exchange(curIndex, leftIndex)
      }
      return min
    }

    while(this.heap[leftIndex] < this.heap[curIndex] || this.heap[rightIndex] < this.heap[curIndex]) {
      let minIndex = leftIndex < rightIndex ? leftIndex : rightIndex;
      this.exchange(curIndex, minIndex)

      curIndex = minIndex;
      leftIndex = curIndex * 2;
      rightIndex = curIndex * 2 + 1;
    }

    return min
  }


}