ヒープと優先度付きキューを初心者向けに解説！データ構造の基礎を理解しよう

100
       /   \
     80    90
    /  \   /
   50  70 60

# 配列表現
heap = [100, 80, 90, 50, 70, 60]

追加: A, B, C, D
取り出し: A → B → C → D
（入れた順番に取り出される）

追加: A(優先度3), B(優先度1), C(優先度5), D(優先度2)
取り出し: C → A → D → B
（優先度の高い順に取り出される）

import heapq

# 空のヒープを作成
heap = []

# 要素の追加
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)

print(heap)  # [1, 3, 7, 5] - 最小ヒープの配列表現

# 最小値の取得と削除
min_value = heapq.heappop(heap)
print(f"最小値: {min_value}")  # 最小値: 1
print(heap)  # [3, 5, 7]

import heapq

# 通常のリスト
data = [9, 5, 6, 2, 3, 7, 1, 4]

# リストをヒープに変換
heapq.heapify(data)

print(data)  # [1, 2, 6, 4, 3, 7, 9, 5]

# 最小値から順に取り出す
while data:
    print(heapq.heappop(data), end=' ')
# 出力: 1 2 3 4 5 6 7 9

import heapq

class PriorityQueue:
    def __init__(self):
        self.heap = []
        self.counter = 0  # 同じ優先度の要素の順序を保つため
    
    def push(self, item, priority):
        """要素を優先度付きで追加"""
        # (優先度, カウンタ, アイテム)のタプルを追加
        # カウンタで同優先度の場合の順序を保証
        heapq.heappush(self.heap, (priority, self.counter, item))
        self.counter += 1
    
    def pop(self):
        """最も優先度の高い要素を取り出す"""
        if self.heap:
            priority, counter, item = heapq.heappop(self.heap)
            return item
        raise IndexError("優先度付きキューが空です")
    
    def peek(self):
        """最も優先度の高い要素を確認（削除しない）"""
        if self.heap:
            priority, counter, item = self.heap[0]
            return item
        raise IndexError("優先度付きキューが空です")
    
    def is_empty(self):
        """キューが空かどうか確認"""
        return len(self.heap) == 0

# 使用例: タスク管理システム
tasks = PriorityQueue()

tasks.push("レポート作成", priority=2)
tasks.push("緊急バグ修正", priority=1)  # 最高優先度
tasks.push("コードレビュー", priority=3)
tasks.push("会議準備", priority=2)

print("タスクを優先度順に処理:")
while not tasks.is_empty():
    task = tasks.pop()
    print(f"- {task}")

# 出力:
# タスクを優先度順に処理:
# - 緊急バグ修正
# - レポート作成
# - 会議準備
# - コードレビュー

#include <iostream>
#include <queue>
#include <vector>

int main()
{
    // 最大ヒープ（デフォルト）
    std::priority_queue<int> maxHeap;
    
    // 要素の追加
    maxHeap.push(5);
    maxHeap.push(3);
    maxHeap.push(7);
    maxHeap.push(1);
    
    std::cout << "最大値: " << maxHeap.top() << std::endl;  // 7
    
    // 要素を順に取り出す
    std::cout << "要素を大きい順に取り出し: ";
    while (!maxHeap.empty())
    {
        std::cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    std::cout << std::endl;
    // 出力: 7 5 3 1
    
    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <functional>  // std::greaterを使うため

int main()
{
    // 最小ヒープの作成
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
    
    minHeap.push(5);
    minHeap.push(3);
    minHeap.push(7);
    minHeap.push(1);
    
    std::cout << "最小値: " << minHeap.top() << std::endl;  // 1
    
    std::cout << "要素を小さい順に取り出し: ";
    while (!minHeap.empty())
    {
        std::cout << minHeap.top() << " ";
        minHeap.pop();
    }
    std::cout << std::endl;
    // 出力: 1 3 5 7
    
    return 0;
}

#include <iostream>
#include <queue>
#include <string>

// タスクを表す構造体
struct Task
{
    std::string name;
    int priority;
    
    Task(std::string n, int p) : name(n), priority(p) {}
};

// 比較関数（優先度が高いものを優先）
struct CompareTask
{
    bool operator()(const Task& a, const Task& b)
    {
        // 優先度が小さいほど優先度が高いとする
        return a.priority > b.priority;
    }
};

int main()
{
    std::priority_queue<Task, std::vector<Task>, CompareTask> taskQueue;
    
    // タスクの追加
    taskQueue.push(Task("レポート作成", 2));
    taskQueue.push(Task("緊急バグ修正", 1));
    taskQueue.push(Task("コードレビュー", 3));
    taskQueue.push(Task("会議準備", 2));
    
    std::cout << "タスクを優先度順に処理:" << std::endl;
    while (!taskQueue.empty())
    {
        Task task = taskQueue.top();
        std::cout << "- " << task.name 
                  << " (優先度: " << task.priority << ")" 
                  << std::endl;
        taskQueue.pop();
    }
    
    return 0;
}

// 出力:
// タスクを優先度順に処理:
// - 緊急バグ修正 (優先度: 1)
// - レポート作成 (優先度: 2)
// - 会議準備 (優先度: 2)
// - コードレビュー (優先度: 3)

import heapq
from collections import defaultdict

def dijkstra(graph, start):
    """
    ダイクストラ法で最短距離を求める
    
    Args:
        graph: 隣接リスト形式のグラフ
        start: 始点のノード
    
    Returns:
        各ノードへの最短距離の辞書
    """
    # 各ノードへの最短距離（初期値は無限大）
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    
    # 優先度付きキュー（距離, ノード）
    pq = [(0, start)]
    
    # 訪問済みノードの集合
    visited = set()
    
    while pq:
        # 最も距離の短いノードを取得
        current_dist, current_node = heapq.heappop(pq)
        
        # すでに訪問済みならスキップ
        if current_node in visited:
            continue
        
        visited.add(current_node)
        
        # 隣接ノードを確認
        for neighbor, weight in graph[current_node]:
            distance = current_dist + weight
            
            # より短い経路が見つかった場合
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    
    return distances

# グラフの定義（隣接リスト形式）
# graph[ノード] = [(隣接ノード, 重み), ...]
graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8), ('E', 10)],
    'D': [('B', 5), ('C', 8), ('E', 2)],
    'E': [('C', 10), ('D', 2)]
}

# 始点'A'から各ノードへの最短距離を計算
distances = dijkstra(graph, 'A')

print("始点Aから各ノードへの最短距離:")
for node, dist in sorted(distances.items()):
    print(f"{node}: {dist}")

# 出力:
# 始点Aから各ノードへの最短距離:
# A: 0
# B: 3
# C: 2
# D: 8
# E: 10

def heapify(arr, n, i):
    """
    部分木をヒープ化する
    
    Args:
        arr: 配列
        n: ヒープのサイズ
        i: ルートのインデックス
    """
    largest = i  # 最大値を保持するインデックス
    left = 2 * i + 1  # 左の子
    right = 2 * i + 2  # 右の子
    
    # 左の子が存在し、ルートより大きい場合
    if left < n and arr[left] > arr[largest]:
        largest = left
    
    # 右の子が存在し、現在の最大値より大きい場合
    if right < n and arr[right] > arr[largest]:
        largest = right
    
    # 最大値がルートでない場合、交換してヒープ化
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    """
    ヒープソートを実行
    
    Args:
        arr: ソート対象の配列
    
    Returns:
        ソート済み配列
    """
    n = len(arr)
    
    # 最大ヒープを構築
    # 最後の非葉ノードから開始
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    
    # 要素を一つずつ取り出す
    for i in range(n - 1, 0, -1):
        # 現在のルート（最大値）を末尾に移動
        arr[0], arr[i] = arr[i], arr[0]
        # 縮小したヒープでヒープ化
        heapify(arr, i, 0)
    
    return arr

# 使用例
data = [12, 11, 13, 5, 6, 7]
print("ソート前:", data)

sorted_data = heap_sort(data)
print("ソート後:", sorted_data)

# 出力:
# ソート前: [12, 11, 13, 5, 6, 7]
# ソート後: [5, 6, 7, 11, 12, 13]