이전 기사에서 Binary Search Tree에 대해 썼고 내 Chrome 확장 프로그램에 구현할 수 있는지 확인했습니다. 간단한 이진 검색 트리는 내 프로젝트에 완벽하지 않았지만 트리 구조 내의 일부 기능이 프로젝트에 유용하다는 것을 발견했습니다.

현재 다음과 같은 배열에 객체로 기본 데이터를 저장하고 있습니다.

// Result of console.log(main-data)
(4)[{...}, {...}, {...}, {...}]
0: {category: "cat1", id: "4", meaning: "information of the vocabulary.", tag: ["tag1", "tag2"], word: "Example Vocab 1"}
1: {category: "cat3", id: "3", meaning: "Hello World", tag: ["tag1", "tag4"], word: "Example Vocab 2"}
2: {category: "cat2", id: "2", meaning: "This is new vocabulary.", tag: ["tag4"], word: "Example"}
3: {category: "cat4", id: "1", meaning: "You can write anything.", tag: ["tag2", "tag4", "tag5"], word: "Sample"}

이 상황에서 삽입과 삭제는 O(n)을 취한다. 따라서 나는 여전히 희망적으로 O(1)인 데이터 구조를 찾고 있습니다.

Binary search tree 이후에 배운 것은 Binary Heaps였습니다. 이 기사에서는 적합할지 여부에 대해 생각하려고합니다.

이진 힙이란 무엇입니까?

힙은 트리 데이터 유형 내의 범주 중 하나이며 이진 힙은 힙으로 분류됩니다. 이진 힙은 이진 트리의 형태를 취합니다.



각 값이 인덱스를 갖도록 배열로 구현할 수 있습니다.
그리고 이진 검색 트리와 동일하게 각 값은 0~2개의 하위 항목을 갖지만 2개 이하입니다.

이진 힙이 최대 이진 힙인 경우 상위 노드는 항상 하위 노드보다 큽니다. 이진 힙이 최소 이진 힙인 경우 상위 노드는 항상 하위 노드보다 작습니다.



이러한 기능은 최대 수를 찾는 데 이진 힙을 잘 만들고 최대 수를 제거하거나 새 수를 삽입할 때 목록을 계속 업데이트합니다.

최대 수 제거

배열에서 가장 큰 숫자를 제거할 때 다음으로 가장 큰 숫자가 무엇인지 알고 싶습니다. 아마도 자식 노드 중 하나를 보고 가장 큰 숫자로 직접 배치할 수 있지만 나머지 순서가 엉망이 됩니다.

목록의 시작 부분에 다음으로 큰 숫자를 배치하고 목록을 엉망으로 만들지 않으려면 버블 다운 방법을 구현할 수 있습니다. 먼저 배열의 마지막 숫자를 목록의 시작 부분에 배치하고 올바른 위치를 찾을 때까지 숫자를 가라앉힐 수 있습니다.

버블 다운 단계

어레이를 정렬하는 데 몇 단계만 필요합니다.

(1) 배열의 마지막 숫자(여기서는 대상이라고 함)를 루트에 배치합니다.
(2) 타겟과 자식을 비교합니다.
- 그 중 하나가 대상보다 큰 경우 대상과 더 큰 자식을 교체하십시오.
- 둘 다 대상보다 크면 대상과 가장 큰 자식을 바꿉니다.
- 두 아이 모두 목표보다 작다면 그것이 정확한 지점이 될 것입니다.

번호 삽입

새로운 난수를 배열에 추가할 때 버블업 방법을 구현하여 올바른 위치를 찾고 전체 배열을 원래대로 정렬된 상태로 유지할 수 있습니다.

버블업 단계

버블 다운 방식과 정반대입니다.

(1) 먼저 배열 끝에 새 번호를 삽입합니다.
(2) 대상 번호와 상위 번호를 비교합니다.
- 부모 번호가 목표 번호보다 작으면 서로 교환합니다.
- 부모 숫자가 목표 숫자보다 크면 올바른 위치에 있는 것입니다.

기본 구현

배열로 구현할 것이므로 MaxBinaryHeap 클래스만 초기화하면 됩니다.

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

최대 구현 제거

버블다운 방법을 사용하면 O(log n)의 시간 복잡도가 필요합니다.

removeMax() {
    let removed = this.heap[0];
    let end = this.heap.pop();
    if (this.heap.length > 0) {
        this.heap[0] = end;
        this.bubbleDown();
    }
    return removed;
}

버블다운 구현

bubbleDown() {
    let targetIdx = 0;
    while (true) {
        let target = this.heap[targetIdx];
        let leftChildIdx = targetIdx * 2 + 1;
        let rightChildIdx = targetIdx * 2 + 2;
        let left = this.heap[leftChildIdx];
        let right = this.heap[rightChildIdx];
        let swap = null;
        if (leftChildIdx < this.heap.length && target < left){
            swap = leftChildIdx;
        }
        if (rightChildIdx < this.heap.length && target < right && left < right){
            swap = rightChildIdx;
        }
        if (swap === null) break;
        this.heap[targetIdx] = this.heap[swap];
        this.heap[swap] = target;
        targetIdx = swap;
    }
}

삽입 구현

버블업 방식으로 삽입도 O(log n)이다.

insert(val) {
    this.heap.push(val);
    this.bubbleUp();
}

버블업 구현

bubbleUp() {
    let targetIdx = this.heap.length - 1;
    let target = this.heap[targetIdx]
    while(targetIdx > 0){
        let parentIdx = Math.floor((targetIdx - 1) / 2);
        let parent = this.heap[parentIdx]
        if (target > parent) {
            this.heap[parentIdx] = target;
            this.heap[targetIdx] = parent;
            targetIdx = parentIdx;
        }
        if (target <= parent) break;
    }
}

결론

우선 순위 큐는 Binary Heap을 사용하여 효율적으로 구현할 수 있지만 내 Chrome 확장 프로그램에는 우선 순위가 없으며 목록 중간에 있는 요소를 제거할 때도 효율적이어야 합니다.
이번에는 Binary Heap을 구현하지 않겠지만 Heap 데이터 구조 자체가 엄청나게 사용되므로 확실히 연습할 가치가 있습니다.

참조

JavaScript Algorithms and Data Structures Masterclass (Udemy)
List of data structures (Wikipedia)