Heap이란❓

힙은 최댓값/최소값을 빠르게 찾아내기 위해 고안된 완전이진트리 자료구조이다. 힙은 최대/최소의 값을 검색하는데 O(1) 의 시간복잡도를 가진다. 이때 값을 얻기 위해 pop을 하게 되면 O(logN)의 시간이 걸린다. 또한 맨 처음 펼쳐진 N개의 값들을 힙에 세팅해 주어야 하므로 N 의 시간이 더 걸리게 된다. 그렇기 때문에 힙의 시간복잡도는 O(NlogN)이라고 이야기 한다.

💡 구현

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

<aside> 💡 2를 나누고 math.floor로 소수점을 제외하면 같은 값이 나오는 수가 부모의 index이다.

</aside>

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

• 가장 상단, 하단에 있는 값을 추출하는 과정이기에 this.heap.length - 1을 index로 사용하고 해당 index로 다시 heap에서 찾는 등 index와 index 값을 확실히 해야 한다.
• 예를 들어 현재의 위치를 나타낸다고 해서 단순히 cur이라고 정의할 것이 아닌 curIdx 등으로 index라는 것을 확실히 해야 나중에 헷갈리지 않는다.

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

• 가장 상단, 하단의 값을 추출하기 위해 정반대에 위치한 노드와 순서를 바꿔줘야 하는 일이 빈번하게 발생한다.
• 하지만 단순히 빈번하게 발생한다고 해서 무조건 함수로 빼는 것이 옳은가?