TypeScript中級

中級 TypeScriptで学ぶデータ構造｜練習問題編

 

導入

データ構造は、効率的なアルゴリズムを実現するための基盤です。特に、業務アプリケーションでは、データの取り扱いや処理の効率が求められます。本記事では、中級レベルのTypeScriptを使用して、実務で遭遇しやすいデータ構造の具体的なケースを取り上げ、その運用方法を探ります。特に、ツリー構造の一種であるヒープを取り上げ、具体的な利用シーンを通じて理解を深めます。

教科書レベルの解説（データ構造）

重要な概念の整理

ヒープは、完全二分木の特性を持ちながら、特定の順序を保つデータ構造です。最大ヒープでは親ノードが子ノードよりも大きく、最小ヒープではその逆になります。ヒープは優先度キューの実装によく利用され、タスクの優先順位に基づいて処理を行う際に非常に有用です。このデータ構造を使用することで、効率的な要素の挿入や削除が可能になります。

コード例（TypeScript）


class MaxHeap {
    private heap: number[] = [];

    insert(num: number): void {
        this.heap.push(num);
        this.bubbleUp();
    }

    private bubbleUp(): void {
        let index = this.heap.length - 1;
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.heap[index] <= this.heap[parentIndex]) break;
            [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
            index = parentIndex;
        }
    }

    extractMax(): number | null {
        if (this.heap.length === 0) return null;
        const max = this.heap[0];
        const end = this.heap.pop()!;
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.bubbleDown();
        }
        return max;
    }

    private bubbleDown(): void {
        let index = 0;
        const length = this.heap.length;
        const element = this.heap[0];

        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let leftChild, rightChild;
            let swap = null;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild > element) {
                    swap = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild > element) || 
                    (swap !== null && rightChild > leftChild!)) {
                    swap = rightChildIndex;
                }
            }

            if (swap === null) break;
            [this.heap[index], this.heap[swap]] = [this.heap[swap], this.heap[index]];
            index = swap;
        }
    }
}

コードの行ごとの解説

  1. class MaxHeap { – ヒープのクラスを定義します。
  2. private heap: number[] = []; – ヒープを表す配列を初期化します。
  3. insert(num: number): void { – ヒープに新しい要素を挿入するメソッドです。
  4. this.heap.push(num); – 新しい要素を配列の末尾に追加します。
  5. this.bubbleUp(); – 挿入後に要素の位置を調整します。
  6. private bubbleUp(): void { – 要素を上に移動させるプライベートメソッドです。
  7. extractMax(): number | null { – 最大値を取り出すメソッドです。
  8. this.heap.pop()! – ヒープの最後の要素を取り出します。
  9. this.bubbleDown(); – 最大値を取り出した後に要素の位置を調整します。
  10. private bubbleDown(): void { – 要素を下に移動させるプライベートメソッドです。

練習問題編

以下の練習問題に挑戦し、ヒープの理解を深めましょう。

  1. 問題1: ヒープに10, 20, 5, 30, 15を挿入した後のヒープの状態を示してください。
  2. 模範解答: [30, 20, 5, 10, 15] です。
  3. 問題2: ヒープから最大値を取り出した後の状態を示してください。
  4. 模範解答: [20, 15, 5, 10] です。
  5. 問題3: ヒープに新たに25を挿入した後の状態を示してください。
  6. 模範解答: [25, 20, 5, 10, 15] です。
  7. 問題4: ヒープから最大値を取り出した後、再度最大値を取り出した際の状態を示してください。
  8. 模範解答: [20, 15, 5] です。

まとめ

  • ヒープは優先度キューの実装に適したデータ構造です。
  • 挿入や削除の操作が効率的に行えるため、実務において非常に有用です。
  • 具体的なケーススタディを通じて、ヒープの使い方を理解することが重要です。
RELATED POST