アルゴリズムとデータ構造(java)


# 基本的なデータ構造とアルゴリズムの基礎知識

本記事では、バイナリーサーチ（Binary Search）、バイナリーツリー（Binary Tree）、ヒープ（Heap）、スタック（Stack）、キュー（Queue）について、それぞれの概要と平均計算量をオーダー記法（Big O記法）で解説します。また、各データ構造やアルゴリズムのJava実装例も紹介します。

## バイナリーサーチ（Binary Search）

### 概要

バイナリーサーチは、ソートされた配列に対して効率的に要素を探索するアルゴリズムです。データを半分に分割し、探索対象の値と中央の値を比較することで、探索範囲を逐次的に半減させていきます。反復的（イテレーティブ）および再帰的な実装が可能です。

### 平均計算量
- **時間計算量**: O(log n)

バイナリーサーチは、探索範囲を半分に絞り込む操作を繰り返すため、データのサイズnに対してlog n回の比較が必要です。したがって、平均的なケースではO(log n)の時間計算量となります。ただし、データがソートされている必要があります。

### バイナリーサーチのJava実装

#### 反復的実装

```java
public class BinarySearchIterative {
    /**
     * バイナリサーチ（反復的）
     * ソートされた配列内で指定された値を探索し、見つかったインデックスを返す。
     * 見つからない場合は -1 を返す。
     *
     * @param numbers ソートされた整数配列
     * @param value   探索する値
     * @return 見つかったインデックスまたは -1
     */
    public static int binarySearchIterative(int[] numbers, int value) {
        int left = 0;
        int right = numbers.length - 1;

        while (left <= right) {
            int mid = left + (right - left) / 2; // オーバーフローを防ぐ
            if (numbers[mid] == value) {
                return mid;
            } else if (numbers[mid] < value) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 5, 7, 9, 11, 15, 20, 24};
        int valueToSearch = 15;

        int result = binarySearchIterative(nums, valueToSearch);
        System.out.println("Binary Search Iterative Index: " + result); // 出力: 6
    }
}
```

#### 再帰的実装

```java
public class BinarySearchRecursive {
    /**
     * バイナリサーチ（再帰的）
     * ソートされた配列内で指定された値を探索し、見つかったインデックスを返す。
     * 見つからない場合は -1 を返す。
     *
     * @param numbers ソートされた整数配列
     * @param value   探索する値
     * @return 見つかったインデックスまたは -1
     */
    public static int binarySearchRecursive(int[] numbers, int value) {
        return _binarySearchRecursive(numbers, value, 0, numbers.length - 1);
    }

    private static int _binarySearchRecursive(int[] numbers, int value, int left, int right) {
        if (left > right) {
            return -1;
        }

        int mid = left + (right - left) / 2; // オーバーフローを防ぐ
        if (numbers[mid] == value) {
            return mid;
        } else if (numbers[mid] < value) {
            return _binarySearchRecursive(numbers, value, mid + 1, right);
        } else {
            return _binarySearchRecursive(numbers, value, left, mid - 1);
        }
    }

    public static void main(String[] args) {
        int[] nums = {0, 1, 5, 7, 9, 11, 15, 20, 24};
        int valueToSearch = 15;

        int result = binarySearchRecursive(nums, valueToSearch);
        System.out.println("Binary Search Recursive Index: " + result); // 出力: 6
    }
}
```

## バイナリーツリー（Binary Tree）

### 概要

バイナリーツリーは、各ノードが最大で2つの子ノード（左子と右子）を持つ階層型データ構造です。探索、挿入、削除が効率的に行えるため、多くのアルゴリズムやデータ構造の基盤として利用されます。特に、**二分探索木（Binary Search Tree, BST）**は、ソートされたデータの格納と高速な検索を可能にします。

### 平均計算量
- **探索、挿入、削除**: O(log n)

バイナリーツリーがバランスされている場合、各操作はツリーの高さに依存し、平均的なケースではO(log n)の時間計算量となります。ただし、バランスが崩れた場合（例えば、すべてのノードが一方向に偏っている場合）は、最悪ケースでO(n)となります。

### 二分探索木のJava実装

```java
class TreeNode {
    int value;
    TreeNode left, right;

    public TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

public class BinarySearchTree {
    TreeNode root;

    BinarySearchTree() {
        root = null;
    }

    /**
     * 二分探索木への挿入
     *
     * @param root  現在のノード
     * @param value 挿入する値
     * @return 挿入後のノード
     */
    TreeNode insert(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.value)
            root.left = insert(root.left, value);
        else if (value > root.value)
            root.right = insert(root.right, value);

        return root;
    }

    /**
     * 中間順巡回（In-order Traversal）
     *
     * @param root 現在のノード
     */
    void inorder(TreeNode root) {
        if (root != null) {
            inorder(root.left);
            System.out.print(root.value + " ");
            inorder(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        /* 二分探索木を構築
              50
           /      \
         30        70
         /  \     /  \
       20   40  60   80 */
        tree.root = tree.insert(tree.root, 50);
        tree.insert(tree.root, 30);
        tree.insert(tree.root, 20);
        tree.insert(tree.root, 40);
        tree.insert(tree.root, 70);
        tree.insert(tree.root, 60);
        tree.insert(tree.root, 80);

        // 中間順巡回の結果を表示
        tree.inorder(tree.root); // 出力: 20 30 40 50 60 70 80 
    }
}
```

## ヒープ（Heap）

### 概要

ヒープは、完全二分木を基にしたデータ構造で、特に**最大ヒープ（Max Heap）や最小ヒープ（Min Heap）**が知られています。ヒープは優先度キューの実装やヒープソート、グラフアルゴリズムなど、さまざまな場面で利用されます。最大ヒープでは親ノードが子ノードよりも大きい値を持ち、最小ヒープではその逆となります。

### 平均計算量
- **挿入、削除**: O(log n)

ヒープに要素を挿入したり削除したりする際には、ヒープの性質を維持するために再ヒープ化（ヒープの再構築）が必要で、これにはツリーの高さに比例する時間がかかります。完全二分木であるため、ツリーの高さはlog nです。

### 最大ヒープ（Max Heap）のJava実装

```java
public class MaxHeap {
    private int[] heap;
    private int size;
    private int maxsize
        // コンストラクタ
    public MaxHeap(int maxsize) {
        this.maxsize = maxsize;
        this.size = 0;
        heap = new int[this.maxsize + 1];
        heap[0] = Integer.MAX_VALUE; // 1-based indexing
    }

    // 親ノードのインデックス
    private int parent(int pos) {
        return pos / 2;
    }

    // 左子ノードのインデックス
    private int leftChild(int pos) {
        return 2 * pos;
    }

    // 右子ノードのインデックス
    private int rightChild(int pos) {
        return 2 * pos + 1;
    }

    // ノードの交換
    private void swap(int fpos, int spos) {
        int tmp;
        tmp = heap[fpos];
        heap[fpos] = heap[spos];
        heap[spos] = tmp;
    }

    // ヒープに挿入
    public void insert(int element) {
        if (size >= maxsize) {
            System.out.println("Heap is full. Cannot insert " + element);
            return;
        }
        heap[++size] = element;
        int current = size;

        // ヒープの性質を維持するために上昇
        while (heap[current] > heap[parent(current)]) {
            swap(current, parent(current));
            current = parent(current);
        }
    }

    // ヒープから最大値を削除
    public int extractMax() {
        if (size == 0) {
            System.out.println("Heap is empty.");
            return -1;
        }
        int popped = heap[1];
        heap[1] = heap[size--];
        maxHeapify(1);
        return popped;
    }

    // ヒープの性質を維持するためのメソッド
    private void maxHeapify(int pos) {
        if (pos >= (size / 2) && pos <= size)
            return;

        if (heap[pos] < heap[leftChild(pos)] ||
            heap[pos] < heap[rightChild(pos)]) {

            if (heap[leftChild(pos)] > heap[rightChild(pos)]) {
                swap(pos, leftChild(pos));
                maxHeapify(leftChild(pos));
            } else {
                swap(pos, rightChild(pos));
                maxHeapify(rightChild(pos));
            }
        }
    }

    // ヒープの内容を表示
    public void printHeap() {
        for (int i = 1; i <= size / 2; i++) {
            System.out.print(
                " PARENT : " + heap[i] +
                " LEFT CHILD : " + heap[2 * i] +
                " RIGHT CHILD :" + heap[2 * i + 1]);
            System.out.println();
        }
    }

    public static void main(String[] args) {
        MaxHeap maxHeap = new MaxHeap(15);

        /* ヒープを構築
              10
           /      \
         20        30
        /  \      /  \
      40   50   60   70 */
        maxHeap.insert(10);
        maxHeap.insert(20);
        maxHeap.insert(30);
        maxHeap.insert(40);
        maxHeap.insert(50);
        maxHeap.insert(60);
        maxHeap.insert(70);

        // ヒープの内容を表示
        maxHeap.printHeap();

        // 最大値を抽出
        System.out.println("The max val is " + maxHeap.extractMax()); // 出力: 70
        maxHeap.printHeap();
    }
}
```

## スタック（Stack）

### 概要

スタックは、**後入れ先出し（LIFO: Last-In-First-Out）**のデータ構造です。基本的な操作として、要素の追加（プッシュ）と削除（ポップ）があり、直近に追加された要素が最初に取り出されます。スタックは関数呼び出しの履歴管理や式の評価、バックトラック処理などに利用されます。

### 平均計算量
- **プッシュ**、**ポップ**: O(1)

スタックの基本操作であるプッシュとポップは、常に定数時間で実行できます。

### スタックのJava実装

#### 配列を用いたスタックの実装

```java
public class Stack {
    private int maxSize;
    private int[] stackArray;
    private int top;

    // コンストラクタ
    public Stack(int size) {
        maxSize = size;
        stackArray = new int[maxSize];
        top = -1;
    }

    // プッシュ操作
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is full. Cannot push " + value);
            return;
        }
        stackArray[++top] = value;
    }

    // ポップ操作
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stackArray[top--];
    }

    // ピーク操作（トップの要素を取得）
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty.");
            return -1;
        }
        return stackArray[top];
    }

    // スタックが空かどうかをチェック
    public boolean isEmpty() {
        return (top == -1);
    }

    // スタックが満杯かどうかをチェック
    public boolean isFull() {
        return (top == maxSize - 1);
    }

    public static void main(String[] args) {
        Stack stack = new Stack(5);

        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);
        stack.push(60); // 満杯のためプッシュできない

        System.out.println("Top element is " + stack.peek());

        System.out.println("Popped element: " + stack.pop());
        System.out.println("Popped element: " + stack.pop());

        stack.push(60); // 空きができたのでプッシュ可能
        System.out.println("Top element is " + stack.peek());
    }
}
```

## キュー（Queue）

### 概要

キューは、**先入れ先出し（FIFO: First-In-First-Out）**のデータ構造です。基本的な操作として、要素の追加（エンキュー）と削除（デキュー）があり、最初に追加された要素が最初に取り出されます。キューはプリントジョブの管理や幅優先探索（BFS）、リアルタイムデータ処理などに利用されます。

### 平均計算量
- **エンキュー**、**デキュー**: O(1)

キューの基本操作であるエンキューとデキューは、常に定数時間で実行できます。

### キューのJava実装

#### 配列を用いたキューの実装

```java
public class Queue {
    private int maxSize;
    private int[] queueArray;
    private int front;
    private int rear;
    private int currentSize;

    // コンストラクタ
    public Queue(int size) {
        maxSize = size;
        queueArray = new int[maxSize];
        front = 0;
        rear = -1;
        currentSize = 0;
    }

    // エンキュー操作
    public void enqueue(int value) {
        if (isFull()) {
            System.out.println("Queue is full. Cannot enqueue " + value);
            return;
        }
        rear = (rear + 1) % maxSize;
        queueArray[rear] = value;
        currentSize++;
    }

    // デキュー操作
    public int dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        int value = queueArray[front];
        front = (front + 1) % maxSize;
        currentSize--;
        return value;
    }

    // ピーク操作（フロントの要素を取得）
    public int peek() {
        if (isEmpty()) {
            System.out.println("Queue is empty.");
            return -1;
        }
        return queueArray[front];
    }

    // キューが空かどうかをチェック
    public boolean isEmpty() {
        return (currentSize == 0);
    }

    // キューが満杯かどうかをチェック
    public boolean isFull() {
        return (currentSize == maxSize);
    }

    public static void main(String[] args) {
        Queue queue = new Queue(5);

        queue.enqueue(10);
        queue.enqueue(20);
        queue.enqueue(30);
        queue.enqueue(40);
        queue.enqueue(50);
        queue.enqueue(60); // 満杯のためエンキューできない

        System.out.println("Front element is " + queue.peek());

        System.out.println("Dequeued element: " + queue.dequeue());
        System.out.println("Dequeued element: " + queue.dequeue());

        queue.enqueue(60); // 空きができたのでエンキュー可能
        System.out.println("Front element is " + queue.peek());
    }
}
```


## まとめ

以下に、今回紹介したデータ構造とアルゴリズムの平均計算量をまとめます。

| データ構造・アルゴリズム | 平均時間計算量    |
|-------------------------|-----------------|
| バイナリーサーチ         | O(log n)       |
| バイナリーツリー         | 探索・挿入・削除: O(log n) |
| ヒープ                   | 挿入・削除: O(log n) |
| スタック                 | プッシュ・ポップ: O(1) |
| キュー                   | エンキュー・デキュー: O(1) |

- **バイナリーサーチ**は、ソートされた配列に対して高速な探索を可能にし、O(log n)の時間計算量を持ちます。
- **バイナリーツリー**や**二分探索木（BST）**は、効率的なデータ管理と操作を可能にし、探索や挿入、削除が平均的にO(log n)で行えます。
- **ヒープ**は、優先度キューの実装やヒープソートなどに利用され、挿入と削除がO(log n)の時間で行えます。
- **スタック**と**キュー**は基本的なデータ構造であり、特定の操作に対して常に定数時間で対応可能です。


## 参考資料
- [Wikipedia: バイナリーサーチ](https://en.wikipedia.org/wiki/Binary_search_algorithm)
- [Wikipedia: バイナリーツリー](https://en.wikipedia.org/wiki/Binary_tree)
- [Wikipedia: ヒープ](https://en.wikipedia.org/wiki/Heap_(data_structure))
- [GeeksforGeeks: Binary Search](https://www.geeksforgeeks.org/binary-search/)
- [GeeksforGeeks: Binary Tree](https://www.geeksforgeeks.org/binary-tree-data-structure/)
- [GeeksforGeeks: Heap](https://www.geeksforgeeks.org/heap-data-structure/)
- [GeeksforGeeks: Stack](https://www.geeksforgeeks.org/stack-data-structure/)
- [GeeksforGeeks: Queue](https://www.geeksforgeeks.org/queue-data-structure/)