힙 | Javascript를 이용한 우선순위 대기열 구현

소개

힙은 힙 속성을 만족하는 특별한 트리 기반 데이터 구조입니다.
완전 이진 트리입니다. 즉, 왼쪽에서 오른쪽으로 채워지는 마지막 수준을 제외하고 트리의 모든 수준이 완전히 채워집니다.

힙에는 두 가지 유형이 있습니다.

1. 최대 힙
2. 최소 힙.

최대 힙:

최대 힙에서 특정 노드 I에 대해 I의 값은 해당 하위 노드의 값보다 크거나 같습니다.
이 속성은 이진 트리의 모든 노드에 대해 true여야 합니다. 가장 높은 값(최대값)은 트리의 루트에 있습니다.

최소 힙:

최소 힙에서 특정 노드 I에 대해 I의 값은 해당 하위 노드의 값보다 작거나 같습니다.
이 속성은 이진 트리의 모든 노드에 대해 true여야 합니다. 가장 낮은 값(최소값)은 트리 루트에 있습니다.

삽입 및 삭제 작업을 수행할 때마다 각각 bubbleUp 및 bubbleDown을 수행하므로 우선순위 대기열이라고 부를 수 있습니다.

배열에서도 동일하게 구현할 수 있지만 leftChildindex, rightChildIndex 및 parentIndex를 어떻게 계산합니까?

수식

아이를 얻으려면

2i+1(왼쪽)
2i+2(오른쪽)

부모님을 모시려면

i-1/2

아래에 minHeap 구현을 추가했습니다. 확인하세요.

class MinHeap {
    constructor() {
        this.data = [];
        this.length = 0;
    }

    insert(value) {
        this.data.push(value);
        this.length++;
        this.bubbleUp(this.length-1);
    }

    bubbleUp(index) {

        if (index == 0) {
            return ;
        }

        const parentIndex = this.getParentIndex(index);
        const parentValue = this.data[parentIndex];
        const value = this.data[index];

        if (parentValue > value) {
            this.data[parentIndex] = this.data[index];
            this.data[index] = parentValue;

            this.bubbleUp(parentIndex);
        }
    }

    getParentIndex(index) {
        return Math.floor((index-1)/2);
    }

    getLeftChildIndex(index) {
        return 2*index + 1;
    }

    getRightChildIndex(index) {
        return 2*index + 2;
    }

    bubbleDown(index) {
        if (index >= this.length) {
            return;
        }

        const lIndex = this.getLeftChildIndex(index);
        const rIndex = this.getRightChildIndex(index);

        const lValue = this.data[lIndex];
        const rValue = this.data[rIndex];
        const value = this.data[index];

        if (lValue < rValue && lValue < value) {
            // swap
            this.data[index] = this.data[lIndex];
            this.data[lIndex] = value;
            this.bubbleDown(lIndex);
        } else if (rValue < lValue && rValue < value) {
            this.data[index] = this.data[rIndex];
            this.data[rIndex] = value;
            this.bubbleDown(rIndex)
        }
    }

    delete() {
        if (this.length === 0) {
            return -1;
        }

        const out = this.data[0];
        if (this.length == 1) {
            this.data = [];
            this.length = 0;
            return out;
        }

        this.data[0] = this.data[this.length-1];
        this.length--;
        this.bubbleDown(0);
    }
}

const test = new MinHeap();

test.insert(50);
test.insert(100);
test.insert(101);
test.insert(20);
test.insert(110);
console.log(test)
test.delete();
console.log('---------After Delete -------')
console.log(test)
/*
MinHeap { data: [ 20, 50, 101, 100, 110 ], length: 5 }
---------After Delete -------
MinHeap { data: [ 50, 100, 101, 110, 110 ], length: 4 }
*/

질문이 있으시면 언제든지 연락주세요.

위 내용은 힙 | Javascript를 이용한 우선순위 대기열 구현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!