JS로 Heap 구현하기

Heap이란❓

💡 구현

//max heap
export default class MyHeap {
    constructor() {
        this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
    }
    size() {
        return this.heap.length;
    }
    push(node) {
        this.heap.push(node);
        let curIdx = this.heap.length - 1;
        let parentIdx = Math.floor((curIdx - 1) / 2);

        while (this.heap[parentIdx] < this.heap[curIdx]) {
            [this.heap[parentIdx], this.heap[curIdx]] = [this.heap[curIdx], this.heap[parentIdx]];
            curIdx = parentIdx;
            parentIdx = Math.floor((curIdx - 1) / 2);
        }
    }

    pop() {
        const lastIdx = this.heap.length - 1;
        let curIdx = 0;
        [this.heap[curIdx], this.heap[lastIdx]] = [this.heap[lastIdx], this.heap[curIdx]];
        const result = this.heap.pop();

        while (curIdx < lastIdx) {
            let leftIdx = curIdx * 2 + 1;
            let rightIdx = curIdx * 2 + 2;
            if (!this.heap[leftIdx]) break;
            if (!this.heap[rightIdx]) {
                if (this.heap[curIdx] < this.heap[leftIdx]) {
                    [this.heap[curIdx], this.heap[leftIdx]] = [this.heap[leftIdx], this.heap[curIdx]];
                    curIdx = leftIdx;
                }
                break;
            }

            if (this.heap[curIdx] < this.heap[leftIdx] || this.heap[curIdx] < this.heap[rightIdx]) {
                const maxIdx = this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
                [this.heap[curIdx], this.heap[maxIdx]] = [this.heap[maxIdx], this.heap[curIdx]];
                curIdx = maxIdx;
            }
            break;
        }
        return result;

    }
}

🍒 구현 포인트

부모 자식을 정하는 기준은 짝수, 홀수

• 앞서서 힙은 배열을 이용해 완전 이진 트리 형태로 구현한다고 했다

• 이진 트리이기 때문에 당연히 부모와 자식 노드가 발생하는데, 힙의 경우엔 보통의 완전 이진 트리와는 다르게 반정렬 상태(느슨한 정렬 상태)를 유지한다.

• 이는 최대힙이라면 큰 값이 부모 노드쪽에, 최소힙이라면 작은 값이 부모 노드 쪽에 배치되는 것만 유지하고 왼쪽 자식과 오른쪽 자식은 부모 노드보다 작은 값을 유지하기만 하면 된다.

• 그렇다면 배열을 이용해 어떻게 힙을 구현할 수 있을까?

• 알고리즘 문제에서 배열의 첫번째 값은 비워두는 경우가 종종 있다. 이는 배열의 첫번째 요소가 가지는 index는 0이기 때문에 '1번째' 라는 말과 인지부조화가 생기기에 계산의 편의성을 위해 그러한 경향을 띄는 편이다.

• 배열의 첫 원소는 사용하지 않으므로 부모와 자식 간 다음의 관계가 성립한다.
• 왼쪽 자식의 index = 부모 index * 2 + 1
• 오른쪽 자식의 index = (부모 index * 2) + 2
• 부모의 index = Math.floor(자식의 인덱스 - 1 / 2)

index와 index에 있는 값 변수명 확실하게 하기

• 가장 상단, 하단에 있는 값을 추출하는 과정이기에 this.heap.length - 1을 index로 사용하고 해당 index로 다시 heap에서 찾는 등 index와 index 값을 확실히 해야 한다.

• 예를 들어 현재의 위치를 나타낸다고 해서 단순히 cur이라고 정의할 것이 아닌 curIdx 등으로 index라는 것을 확실히 해야 나중에 헷갈리지 않는다.

swipe 역할을 함수로 빼는 것이 옳은가?

• 가장 상단, 하단의 값을 추출하기 위해 정반대에 위치한 노드와 순서를 바꿔줘야 하는 일이 빈번하게 발생한다.

• 하지만 단순히 빈번하게 발생한다고 해서 무조건 함수로 빼는 것이 옳은가?

• 나의 대답은 NO 이다.

• 코드는 문맥을 파악하기 쉽게 짜야 한다. 만약 특정 로직을 수행하는 코드가 2줄 이상이어서 문맥의 흐름을 방해한다면 함수로 빼는 것이 좋다.

• 하지만 특정 로직을 수행하는 코드가 한줄이라면 얘기가 다르다. 그리고 그 로직 자체로 직관적이라면 더더욱 그렇다.

• 따라서 나는 heap을 구현할 때 swipe 함수를 별도로 만들지 않았다. 순서를 바꾼다는 것이 직관적으로 들어나고 한 줄이라 문맥의 흐름을 방해하지도 않기 때문이다.

pop 구현이 복잡한 이유

• heap은 sort가 아니다!

• 즉, 오름차순, 내림차순으로 정렬되는 것이 아닌 최대값, 최소값을 빠르게 찾을 수 있는 것이다.

• 따라서 최대값, 최소값을 pop하면 그 다음 요소가 최대값, 최소값이라는 보장이 없기 때문에 다시 정렬을 해주는 것이다.

break의 기준

• break는 함수를 빠져 나오는 return과 달리 현재 루프 즉, switch나 for, while문 등을 종료하고 루프에서 빠져나온다.

• heap에서 break가 사용되는 경우는 다음과 같다. 이미 순서가 맞을 땐 위치를 바꿔줄 필요가 없는 것이다.
• 자식이 없을 때
• 왼쪽 자식만 존재하면서 순서가 맞을 때(ex 최대 힙의 경우, 부모노드가 자식노드보다 이미 클 때).
• 양쪽 자식이 모두 존재하면서 순서가 맞을 때.

🔄 리펙토링

• 무한루프 수정
• pop의 while문에서 else처리를 하지않고 break를 걸어 무한루프 발생 → else 처리.

• falsy한 코드 오류
• null이랑 일치할 경우라고 명시해주지 않으면 0인 경우 에러가 날 수 있음 → null 키워드를 사용하여 명시적으로 수정.

//max heap
export default class MyHeap {
  constructor() {
    this.heap = []; // n:parent, 2*n+1:left child, 2*n+2:right child
  }
  size() {
    return this.heap.length;
  }
  push(node) {
    this.heap.push(node);
    let curIdx = this.heap.length - 1;
    let parentIdx = Math.floor((curIdx - 1) / 2);

    while (this.heap[parentIdx] < this.heap[curIdx]) {
      [this.heap[parentIdx], this.heap[curIdx]] = [
        this.heap[curIdx],
        this.heap[parentIdx],
      ];
      curIdx = parentIdx;
      parentIdx = Math.floor((curIdx - 1) / 2);
    }
  }

  pop() {
    let lastIdx = this.heap.length - 1;
    let curIdx = 0;
    [this.heap[curIdx], this.heap[lastIdx]] = [
      this.heap[lastIdx],
      this.heap[curIdx],
    ];
    const result = this.heap.pop();
    lastIdx = this.heap.length - 1;

    while (curIdx < lastIdx) {
      let leftIdx = curIdx * 2 + 1;
      let rightIdx = curIdx * 2 + 2;
      if (this.heap[leftIdx] == null) break;
      if (this.heap[rightIdx] == null) {
        if (this.heap[curIdx] < this.heap[leftIdx]) {
          [this.heap[curIdx], this.heap[leftIdx]] = [
            this.heap[leftIdx],
            this.heap[curIdx],
          ];
        }
        curIdx = leftIdx;
        break;
      }

      if (
        this.heap[curIdx] < this.heap[leftIdx] ||
        this.heap[curIdx] < this.heap[rightIdx]
      ) {
        const maxIdx =
          this.heap[leftIdx] > this.heap[rightIdx] ? leftIdx : rightIdx;
        [this.heap[curIdx], this.heap[maxIdx]] = [
          this.heap[maxIdx],
          this.heap[curIdx],
        ];
        curIdx = maxIdx;
      } else {
        break;
      }
    }
    return result;
  }
}