メインコンテンツへスキップ
Z

ヒープソート ビジュアライザー

ヒープソートのアルゴリズムをアニメーションで可視化。ステップ実行や速度調整、入力データのカスタマイズ、比較・交換回数のライブカウント、擬似コード表示に対応。ブラウザだけでその場に動かせます。

無料 登録不要 クライアントサイド プライバシーに配慮 Updated
/
Comparisons: Swaps / writes: Array accesses:

Code examples

Ready-to-copy reference implementations. Free to use in your own projects and assignments.

使い方

  1. 1 Playを押すと、配列がmaxヒープへと構築され、続いて最大値が順番に取り出されていく様子が再生されます。
  2. 2 Stepを使うと、sift-downの比較処理を1ステップずつ進められます。
  3. 3 Custom inputに任意の数値を入力し、Applyを押すと自分のデータで試せます。
  4. 4 ハイライトされる擬似コードと、リアルタイムの比較・交換回数を確認しながら進められます。

このツールを使う理由

  • 配列がどのようにバイナリヒープ(親はインデックスi、子は2i+1と2i+2)として扱われるかが分かります。
  • 最大値が末尾に移動するたびに、sift-downがヒープの性質をどう復元するかを観察できます。
  • ヒープソートがなぜ追加メモリO(1)だけでO(n log n)を保証できるのか理解できます。
  • すべてブラウザ内で完結します。登録もファイルのアップロードも不要です。

よくある質問

ヒープソートとは何ですか?

ヒープソートは、まず配列からmaxヒープを構築し、その後は根(最大値)を末尾と交換してsift-downでヒープの性質を復元する、という処理を繰り返すアルゴリズムです。これにより、配列の右側から徐々にソート済み領域が広がっていきます。

ヒープソートの時間計算量はどれくらいですか?

最良・平均・最悪のいずれの場合もO(n log n)です。ヒープの構築にO(n)かかり、n回の取り出し処理それぞれにO(log n)かかります。

ヒープソートは安定ソートですか?

いいえ、安定ソートではありません。ヒープ操作では離れた位置にある要素同士を交換するため、同じ値を持つ要素の相対的な順序が入れ替わることがあります。

ヒープソートとクイックソートはどう違いますか?

ヒープソートは最悪の場合でもO(n log n)を保証し、追加メモリもO(1)しか使いません。一方クイックソートは、キャッシュ局所性の良さや係数の小ささから、実際にはより高速に動作することが多いです。

ヒープソート ビジュアライザー とは？

ヒープソート ビジュアライザーは、ヒープソートのアルゴリズムをシミュレートするツールです。配列からmaxヒープを構築した後、根(root)の要素を末尾と交換してsift-down(下方移動)を行い、ヒープの性質を復元する処理を繰り返します。この過程を通じて、保証された計算量O(n log n)を、追加メモリO(1)だけで実現している様子を視覚的に確認できます。

機能

ステップごとのアニメーション

max-heapの構築過程と、各extract(取り出し)およびsift-down(篩い下げ)のステップを確認できます。

計算量

時間計算量: すべてのケースでO(n log n)。空間計算量: O(1)。in-place(その場)、stable(安定)ではありません。

100%プライベート

すべてブラウザ内で完結し、データがアップロードされることはありません。

例

Input

[4, 10, 3, 5, 1]

Output

build max-heap [10,5,3,4,1]; extract max repeatedly → [1, 3, 4, 5, 10] (sorted)

主な用途

  1. 1

    最悪ケースでもO(n log n)、かつin-place

    O(n)の追加メモリを必要とせずにO(n log n)を保証するソートアルゴリズムを確認できます。

  2. 2

    ヒープ構造を学ぶ

    ソートの過程を通じてmax-heapとsift-downを理解できます。

  3. 3

    優先度付きキューとの関連

    ヒープソートとbinary heapによる優先度付きキューを関連付けて理解できます。

概要

Zerethonのヒープソート・ビジュアライザーは、ブラウザ上でアルゴリズムをアニメーション表示します。まずmax-heap(最大ヒープ)を構築し、その後、最大値を配列の末尾へ繰り返し取り出していきます。ヒープソートは最良・平均・最悪のすべてのケースでO(n log n)の時間計算量となり、追加の空間計算量はO(1)です。in-place(その場)ですがstable(安定)ではありません。マージソートの最悪ケース保証と、一定の追加メモリという特徴を兼ね備えています。

カテゴリ
アルゴリズム
料金
無料
プライバシー
ブラウザベース
登録
不要

参考文献

プライバシー

明記されない限り、データがブラウザの外に送信されることはありません。ヒープソート ビジュアライザー は完全にクライアント側で動作します — サーバーへのアップロードなし、ログなし、入力内容のトラッキングなし。

初めての方へ。Big-O 解析付きのステップバイステップ解説を読む: Sorting Algorithms を学ぶ →

比較

Quicksort vs Merge sort

関連ツール

バブルソート ビジュアライザー

バブルソートの動きをアニメーションで確認できるツール。ステップ実行や速度調整、カスタム入力データ、比較・交換回数のリアルタイム表示、擬似コードの表示に対応しています。すべてブラウザ内だけで動作します。

ツールを開く

挿入ソート(Insertion Sort)ビジュアライザー

挿入ソートをアニメーションで可視化。ステップ実行や速度調整、カスタム入力、比較回数・書き込み回数のリアルタイム表示、疑似コード(pseudocode)表示に対応。すべてブラウザ内で完結します。

ツールを開く

選択ソート(Selection Sort)ビジュアライザー

ステップ実行、速度調整、カスタム入力、比較/交換回数のライブカウンター、擬似コードを備えたSelection Sortのアニメーション。すべてブラウザ内だけで完結します。

ツールを開く

マージソート ビジュアライザー

マージソートの動きをアニメーションで再現するツールです。ステップ実行、速度調整、独自のデータ入力、比較・書き込み回数のリアルタイム表示、擬似コード表示に対応。すべてブラウザ上だけで動作します。

ツールを開く

Zerethon Social で作成・共有・成長しよう

無料登録。ポイントを獲得し、実績を集め、世界中のクリエイターとつながりましょう。

無料登録