TypeScript의 일반 바이너리 힙

작지만 유용한 바이너리 힙 구현.

우리의 힙은 항목을 일반 배열로 저장할 것입니다. 1) 아이템 종류와 2) 아이템 비교 기능으로 일반화해 보자. 두 번째 포인트는 최대 및 최소 힙을 모두 생성할 수 있도록 합니다.

class Heap<T> {
    private items: Array<T>;

    public constructor(private compare: (a: T, b: T) => number) {
        this.items = new Array();
    }
}

최대 힙의 경우 비교 함수는 a > b 일 때 양수를 반환하고 최소 힙의 경우 b > a 일 때 양수를 반환할 것으로 예상됩니다. 직접 사전순으로 문자열 키가 있는 키-값 쌍에 액세스해야 한다고 가정합니다. 그런 다음 이러한 최소 힙의 생성은 다음과 같을 수 있습니다.

type HeapItem = {
    key: string;
    value: any;
};

new Heap<HeapItem>((a, b) => b.key.localeCompare(a.key));

또는 숫자 최대 힙이 필요할 때:

new Heap<number>((a, b) => a - b);

이 아름다운 데이터 구조를 만들고자 하는 사람은 다음 두 가지만 기억해야 합니다.

기본 배열 인덱스를 사용하여 부모 또는 자식 트리 노드로 이동하는 방법,

항목을 삽입하거나 제거할 때 힙의 균형을 맞추는 방법입니다.

다음은 균형 잡힌 숫자 키 문자열 값 최대 힙의 예입니다.



각 노드에는 최대 두 개의 하위 노드가 있습니다. 기본 배열 내에 노드 인덱스 i가 있으면 자식 인덱스를 2 * i + 1 및 2 * i + 2 로, 부모 인덱스를 (i - 1) / 2 >> 0 로 계산할 수 있습니다. 0 비트만큼 오른쪽 시프트는 왼쪽 피연산자가 -1.0 보다 클 때 부호뿐만 아니라 분수 부분을 삭제하는 일반적인 JavaScript 방법 중 하나입니다. 따라서 i = 1의 경우 자식 인덱스는 3 및 4 이고 부모 노드 인덱스는 0 입니다.

힙 속성에 따라 각 상위 노드a 및 하위 노드b에 대해 compare(a, b) >= 0 이어야 합니다. 새 항목을 삽입할 때 먼저 기본 배열의 끝에 놓고 힙 속성 만족을 확인하고 필요한 경우 항목을 해당 부모 노드와 교체합니다. 그런 다음 루트까지 계산을 반복합니다.

class Heap<T> {
    public insert(item: T): void {
        const j = this.items.length;
        this.items[j] = item; // put to the end
        heapifyUp(this.items, this.compare, j);
    }
}

function heapifyUp<T>(
    items: Array<T>,
    compare: (a: T, b: T) => number,
    j: number
): void {
    let i = (j - 1) / 2 >> 0; // parent node index
    while (j > 0 && compare(items[i], items[j]) < 0) {
        // restore the property
        [items[i], items[j]] = [items[j], items[i]];

        // go up
        j = i, i = (j - 1) / 2 >> 0;
    }
}

비교 횟수는 트리의 높이, 즉 log2N(N은 항목 수)을 초과할 수 없으므로 삽입 복잡도도 log2N을 초과하지 않습니다.

우선 순위가 가장 높은 항목을 제거할 때 먼저 기본 배열의 마지막 항목을 제거된 항목 위치로 이동한 다음 동일한 스왑 방식으로 루트에서 리프까지 트리의 균형을 맞춥니다.

class Heap<T> {
    public remove(): T | undefined {
        const { items } = this;
        if (items.length === 0) {
            // heap is empty
            return undefined;
        }

        // remember root as the result
        const result = items[0];
        if (items.length > 1) {
            // put the last item in place of the root
            items[0] = items[items.length - 1];
        }

        // truncate the array
        items.length--;
        if (items.length < 2) {
            // nothing to balance
            return result;
        }

        heapifyDown(items, this.compare, 0);
        return result;
    }
}

function heapifyDown<T>(
    items: Array<T>,
    compare: (a: T, b: T) => number,
    i: number, n?: number
): void {
    let j, k: number;
    n = n ?? items.length;
    while (true) {
        j = 2 * i + 1, k = i;
        if (j < n && compare(items[j], items[k]) > 0) {
            // left child violates the property
            k = j;
        }

        j++;
        if (j < n && compare(items[j], items[k]) > 0) {
            // right child violates the property (even more)
            k = j;
        }

        // no property violations
        if (k === i) break;

        // restore the property
        [items[i], items[k]] = [items[k], items[i]];

        // go down
        i = k;
    }
}

여기에서는 각 heapify 반복에서 최대 두 번의 비교가 있으므로 제거의 복잡성은 2log2N을 초과하지 않습니다.

전체 소스 코드와 단위 테스트 코드는 GitHub에서 찾을 수 있습니다.