JavaScriptの配列をProxyでヒープに変換する：初心者向けのアプローチ

English Version.

This article provides a new step - by - step examination of a new implementation of the heap property:
The createHeap function, which utilizes JavaScript's Proxy object to transform a standard array into a fully functional heap. This method enforces the heap structure behind the scene, supports generic types via a custom comparator, and accommodates to a fixed-size length for applications like maintaining top-K elements.
By intercepting array operations, it enables native usage—such as push and pop—while preventing direct assignments that could compromise the structure.This approach is especially advantageous in a large environment where new developers or interns are infamiliar with the heap structure, as it demonstrates and allow advanced language features like generics and proxies in a familiar context.

** Step 1: The Function Initialization
The function begins by defining its parameters and initializing the underlying heap array:
• Comparator(cmp): A function that determines ordering, returning true if the first argument should precede the second in the heap(i.e., for a min - heap, if a is smaller than b).
• Size Limit k: An optional parameter default to Infinity, which caps the heap's capacity.
• Heap Array: An empty array typed based on the comparator's parameters that will hold our elements

function createHeap<T extends (a: any, b: any) => boolean>(cmp: T, k: number = Infinity) {
    const heap: Parameters<T>[] = [];
    // ...
}

** Step 2: Defining the Bubble - Up Function
To maintain the heap property after inserting a new element, a bubble_up function is introduced.This compares the newly added element with its parent and swaps if necessary, ascending the tree until the invariant holds or we reach the top of the tree.

const bubble_up = (arr: Parameters<T>[], i: number) => {
    // Bubble up will ensure that every new item pushed to the array will satisfy the heap property
    while (i > 0) {
        const parent = Math.floor((i - 1) / 2);
        if (cmp(arr[parent], arr[i])) break;
        [arr[parent], arr[i]] = [arr[i], arr[parent]];
        i = parent;
    }
};

• Loop Condition: Continues as long as the current index is not the root.
• Comparison and Swap: Relies on cmp for swapping; breaks if the parent is in its correct position.

** Step 3: Defining the Bubble - Down Mechanism
For extractions or root replacements, bubble_down pushes down the root by comparing it with its children and swapping with the smallest.

const bubble_down = (arr: Parameters<T>[], i: number) => {
    // Bubble down will ensure that when we pop an item from our array, the heap will restructure itself
    // to satisfy its properties
    while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        if (left < arr.length && cmp(arr[left], arr[smallest])) smallest = left;
        if (right < arr.length && cmp(arr[right], arr[smallest])) smallest = right;
        if (smallest === i) break;
        [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
        i = smallest;
    }
};

• Infinite Loop with Break: Break only when the heap is restructured.
• Selection and Swap: Chooses the smallest child; terminates if no swap is needed.

** Step 4: Configuring the Proxy Object
The main logic which intercepts property accesses and assignments:
• Get Trap: Overrides methods like push, pop, and introduces peek, and size.
• Set Trap: Blocks direct index assignments to preserve the heap.

return new Proxy(heap, {
    get(target: Parameters<T>[], prop: string) {
        if (prop === "push") {
            return (val: Parameters<T>) => {
                if (target.length < k) {
                    target.push(val);
                    bubble_up(target, target.length - 1);
                } else {
                    if (cmp(target[0], val)) {
                        target[0] = val;
                        bubble_down(target, 0);
                    }
                }
            };
        }
        if (prop === "pop") {
            // Modifying the pop to return the first element and then swap the last with first and bubbling down
            return () => {
                if (target.length === 0) return undefined;
                if (target.length === 1) return target.pop();
                const val = target[0];
                target[0] = target.pop()!;
                bubble_down(target, 0);
                return val;
            };
        }
        if (prop === "peek") {
            return () => target[0];
        }
        if (prop === "size") return target.length;
    },
    set(target, prop, value) {
        // we prevent regular assignment to the array
        if (typeof prop === 'string' && !isNaN(Number(prop))) {
            throw new Error('Direct assignment not allowed; use push()');
        }
        return Reflect.set(target, prop, value);
    }
});

• Push Logic: Adds and bubbles up if under capacity; otherwise, replaces root if the new value satisfies the comparator logic(for top - K problems).
• Pop Logic: Handles edge cases(empty or single - element heaps) before swapping and bubbling down.
• Peek and Size: Provide easy access to the root and length.
• Set Prevention: Throws an error on direct assignments.

Final Version:

// @params cmp: Function that the heap need to satsify
// @params k: max len of the heap, by default it is set to Infinity
// @returns heap: array satsifies the heap property

function createHeap<T extends (a: any, b: any) => boolean>(cmp: T, k: number = Infinity) {
    const heap: Parameters<T>[] = [];
    const bubble_up = (arr: Parameters<T>[], i: number) => {
        // Bubble up will ensure that every new item pushed to the array will satisfy the heap property
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2)
            if (cmp(arr[parent], arr[i])) break
            [arr[parent], arr[i]] = [arr[i], arr[parent]]
            i = parent
        }
    }
    const bubble_down = (arr: Parameters<T>[], i: number) => {
        // Bubble down will ensure that when we pop an item from our array, the heap will restructure itself
        // to satisfy its properties
        while (true) {
            const left = 2 * i + 1
            const right = 2 * i + 2
            let smallest = i
            if (left < arr.length && cmp(arr[left], arr[smallest])) smallest = left
            if (right < arr.length && cmp(arr[right], arr[smallest])) smallest = right
            if (smallest === i) break
            [arr[smallest], arr[i]] = [arr[i], arr[smallest]]
            i = smallest
        }
    }
    return new Proxy(heap, {
        get(target: Parameters<T>[], prop: string) {
            if (prop === "push") {
                return (val: Parameters<T>) => {
                    if (target.length < k) {
                        target.push(val)
                        bubble_up(target, target.length - 1)
                    } else {
                        if (cmp(target[0], val)) {
                            target[0] = val
                            bubble_down(target, 0)
                        }
                    }
                }
            }
            if (prop === "pop") {
                // Modifying the pop to return the first element and then swap the last with first and bubbling down
                return () => {
                    if (target.length === 0) return undefined
                    if (target.length === 1) return target.pop()
                    const val = target[0]
                    target[0] = target.pop()!
                    bubble_down(target, 0)
                    return val
                }
            }
            if (prop === "peek") {
                return () => target[0]
            }
            if (prop === "size") return target.length
        },
        set(target, prop, value) {
            // we prevent regular assignment to the array
            if (typeof prop === 'string' && !isNaN(Number(prop))) {
                throw new Error('Direct assignment not allowed; use push()');
            }
            return Reflect.set(target, prop, value);
        }
    })
}

Usage Examples:

For numerical data:

const cmp = (a: number, b: number) => a < b;
const heap = createHeap(cmp, 3);
heap.push(10);
heap.push(3);
heap.push(7);
heap.push(1); // Replaces if necessary
console.log(heap.peek()); // 1
console.log(heap.pop());  // 1

For objects:

interface Task { priority: number; }
const cmp = (a: Task, b: Task) => a.priority < b.priority;
const heap = createHeap(cmp);
heap.push({ priority: 5 });
heap.push({ priority: 2 });
console.log(heap.peek().priority); // 2

日本語版

プロキシを使用したTypeScriptにおける汎用ヒープの実装に関する詳細なステップバイステップガイド

この記事では、ヒープ特性の新たな実装について段階的に検証します：
createHeap関数はJavaScriptのProxyオブジェクトを利用し、標準配列を完全な機能を備えたヒープに変換します。この手法はバックグラウンドでヒープ構造を強制し、カスタム比較関数による汎用型をサポートし、上位K要素の維持といった用途向けに固定長に対応します。
配列操作をインターセプトすることで、pushやpopといったネイティブ操作を可能にしながら、構造を損なう可能性のある直接代入を防止します。このアプローチは、新規開発者やインターンがヒープ構造に不慣れな大規模環境において特に有効です。なぜなら、ジェネリクスやプロキシといった高度な言語機能を、馴染み深い文脈で示し、利用可能にするからです。

** ステップ1: 関数の初期化
関数はまずパラメータを定義し、基盤となるヒープ配列を初期化します:
• 比較関数(cmp): 順序を決定する関数。最初の引数がヒープ内で2番目の引数より前に配置されるべき場合（つまり、最小ヒープの場合、aがbより小さい場合）にtrueを返します。
• サイズ制限(k): オプションのパラメータで、デフォルトは無限大。ヒープの容量を制限する。
• ヒープ配列: 比較関数のパラメータに基づいて型付けされた空の配列。要素を格納する。

function createHeap<T extends (a: any, b: any) => boolean>(cmp: T, k: number = Infinity) {
    const heap: Parameters<T>[] = [];
    // 以降のロジック...
}

** ステップ2: バブルアップ関数の定義
新しい要素を挿入した後もヒープ特性を維持するため、バブルアップ関数を導入する。この関数は、新しく追加された要素とその親要素を比較し、必要に応じて交換する。木の上昇を続け、不変条件が成立するか、木の頂点に到達するまでこの処理を繰り返す。

const bubble_up = (arr: Parameters<T>[], i: number) => {
    // バブルアップにより、配列にプッシュされるすべての新規アイテムがヒーププロパティを満たすことが保証される
    while (i > 0) {
        const parent = Math.floor((i - 1) / 2);
        if (cmp(arr[parent], arr[i])) break;
        [arr[parent], arr[i]] = [arr[i], arr[parent]];
        i = parent;
    }
};

• ループ条件：現在のインデックスがルートでない限り継続する。
• 比較と交換：cmp による交換に依存する。親が正しい位置にある場合は中断する。

** ステップ 3：バブルダウン機構の定義
抽出またはルート置換において、bubble_down はルートを子要素と比較し、最小値と交換することでルートを下方に移動させる。

const bubble_down = (arr: Parameters<T>[], i: number) => {
    // バブルダウンにより、配列から要素をポップする際に、ヒープはその性質を満たすよう自身を再構築する
    // ことが保証される
    while (true) {
        const left = 2 * i + 1;
        const right = 2 * i + 2;
        let smallest = i;
        if (left < arr.length && cmp(arr[left], arr[smallest])) smallest = left;
        if (right < arr.length && cmp(arr[right], arr[smallest])) smallest = right;
        if (smallest === i) break;
        [arr[smallest], arr[i]] = [arr[i], arr[smallest]];
        i = smallest;
    }
};

• 無限ループと中断：ヒープの再構築時のみ中断する。
• 選択と交換：最小の子を選択する。交換が不要な場合は終了する。

** ステップ4: プロキシオブジェクトの設定
プロパティアクセスと代入をインターセプトする主要ロジック:
• 取得トラップ: push、popなどのメソッドを上書きし、peekやsizeを導入する。
• 設定トラップ: ヒープを保護するため、直接インデックス代入をブロックする。

return new Proxy(heap, {
    get(target: Parameters<T>[], prop: string) {
        if (prop === "push") {
            return (val: Parameters<T>) => {
                if (target.length < k) {
                    target.push(val);
                    bubble_up(target, target.length - 1);
                } else {
                    if (cmp(target[0], val)) {
                        target[0] = val;
                        bubble_down(target, 0);
                    }
                }
            };
        }
        if (prop === "pop") {
            // ポップ操作を変更し、最初の要素を返した後、最後と最初を交換し、バブリングダウンを行う
            return () => {
                if (target.length === 0) return undefined;
                if (target.length === 1) return target.pop();
                const val = target[0];
                target[0] = target.pop()!;
                bubble_down(target, 0);
                return val;
            };
        }
        if (prop === "peek") {
            return () => target[0];
        }
        if (prop === "size") return target.length;
    },
    set(target, prop, value) {
        // 配列への通常の代入を防止します
        if (typeof prop === 'string' && !isNaN(Number(prop))) {
            throw new Error('Direct assignment not allowed; use push()');
        }
        return Reflect.set(target, prop, value);
    }
});

• プッシュロジック：容量不足の場合に要素を追加・バブルアップする。それ以外の場合、新規値が比較器ロジックを満たす（上位K問題の場合）とルートを置換する。
• ポップロジック：スワップとバブルダウン前に境界条件（空または単一要素のヒープ）を処理する。
• ピークとサイズ：ルートと長さに容易にアクセス可能。
• 設定防止：直接代入時にエラーをスローする。

最終版：

// @params cmp: ヒープが満たすべき関数
// @params k: ヒープの最大長さ。デフォルトは無限大
// @returns heap: ヒープ特性を満たす配列

function createHeap<T extends (a: any, b: any) => boolean>(cmp: T, k: number = Infinity) {
    const heap: Parameters<T>[] = [];
    const bubble_up = (arr: Parameters<T>[], i: number) => {
        // バブルアップにより、配列にプッシュされるすべての新規要素がヒーププロパティを満たすことが保証される
        while (i > 0) {
            const parent = Math.floor((i - 1) / 2)
            if (cmp(arr[parent], arr[i])) break
            [arr[parent], arr[i]] = [arr[i], arr[parent]]
            i = parent
        }
    }
    const bubble_down = (arr: Parameters<T>[], i: number) => {
        // バブルダウンにより、配列から要素をポップする際に、ヒープはその性質を満たすよう自身を再構築する
        // ことが保証される
        while (true) {
            const left = 2 * i + 1
            const right = 2 * i + 2
            let smallest = i
            if (left < arr.length && cmp(arr[left], arr[smallest])) smallest = left
            if (right < arr.length && cmp(arr[right], arr[smallest])) smallest = right
            if (smallest === i) break
            [arr[smallest], arr[i]] = [arr[i], arr[smallest]]
            i = smallest
        }
    }
    return new Proxy(heap, {
        get(target: Parameters<T>[], prop: string) {
            if (prop === "push") {
                return (val: Parameters<T>) => {
                    if (target.length < k) {
                        target.push(val)
                        bubble_up(target, target.length - 1)
                    } else {
                        if (cmp(target[0], val)) {
                            target[0] = val
                            bubble_down(target, 0)
                        }
                    }
                }
            }
            if (prop === "pop") {
                // ポップ操作を変更し、最初の要素を返した後、最後と最初を交換し、バブリングダウンを行う
                return () => {
                    if (target.length === 0) return undefined
                    if (target.length === 1) return target.pop()
                    const val = target[0]
                    target[0] = target.pop()!
                    bubble_down(target, 0)
                    return val
                }
            }
            if (prop === "peek") {
                return () => target[0]
            }
            if (prop === "size") return target.length
        },
        set(target, prop, value) {
            // 配列への通常の代入を防止します
            if (typeof prop === 'string' && !isNaN(Number(prop))) {
                throw new Error('Direct assignment not allowed; use push()');
            }
            return Reflect.set(target, prop, value);
        }
    })
}

使用例：

数値データの場合：

const cmp = (a: number, b: number) => a < b;
const heap = createHeap(cmp, 3);
heap.push(10);
heap.push(3);
heap.push(7);
heap.push(1); // 必要に応じて置き換え
console.log(heap.peek()); // 1
console.log(heap.pop());  // 1

オブジェクトの場合：

interface Task { priority: number; }
const cmp = (a: Task, b: Task) => a.priority < b.priority;
const heap = createHeap(cmp);
heap.push({ priority: 5 });
heap.push({ priority: 2 });
console.log(heap.peek().priority); // 2