基本的なデータ構造とアルゴリズムの基礎知識
本記事では、バイナリーサーチ（Binary Search）、バイナリーツリー（Binary Tree）、ヒープ（Heap）、スタック（Stack）、キュー（Queue）について、それぞれの概要と平均計算量をオーダー記法（Big O記法）で解説します。また、各データ構造やアルゴリズムのJava実装例も紹介します。
バイナリーサーチ（Binary Search）
概要
バイナリーサーチは、ソートされた配列に対して効率的に要素を探索するアルゴリズムです。データを半分に分割し、探索対象の値と中央の値を比較することで、探索範囲を逐次的に半減させていきます。反復的（イテレーティブ）および再帰的な実装が可能です。
平均計算量
- 時間計算量: O(log n)
バイナリーサーチは、探索範囲を半分に絞り込む操作を繰り返すため、データのサイズnに対してlog n回の比較が必要です。したがって、平均的なケースではO(log n)の時間計算量となります。ただし、データがソートされている必要があります。
バイナリーサーチの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
}
}
再帰的実装
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実装
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実装
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実装
配列を用いたスタックの実装
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実装
配列を用いたキューの実装
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)の時間で行えます。
- スタックとキューは基本的なデータ構造であり、特定の操作に対して常に定数時間で対応可能です。