最初に「あい」を学ぶことば日本語でプログラミング入門（Mindで定番アルゴリズム： 優先度付きキュー）

はじめに

本記事シリーズは母国語のプログラミング言語が存在するという文化的価値をアピールするためのもので、プログラミング一般の入門を意図するものではありません。とはいっても題材としては定番アルゴリズムのいくつかを疑似言語ではなくコンパイル・実行可能なプログラミング言語の日本語で書いてみようというたてつけとなります。

Mind（マインド）

プログラミング言語Mind（マインド）は自然な日本語で記述できるスタック指向の軽量中間コードコンパイラ言語です。ただし単語間の分かち書きが必須であくまで形式言語です。逆ポーランド記法¹の範囲で分かち書きされた日本語単語の語順が自然と日本語の語順となるという意味の「自然さ」で書くことができ、独自の軽量中間コードのランタイム実行で非常に高速です。実装言語はCまたはMind。初版の登場は1985年で2025年は生誕４０周年となりました。

Mind（マインド）の入手方法

無償版のMind version 8 (windows版linux版)を下記の公式サイトからダウンロードできます。フリーメールでかまいませんのでメールアドレスをご登録くださいませ。

定番アルゴリズム：優先度付きキューとは

アルゴリズムは、問題を解決するための手順や計算方法を意味します。アルゴリズムにはいくつかの定番ロジックが存在します。

ここではその中のひとつ「優先度付きキュー」を扱ってみます。「優先度付きキュー」（「優先度キュー」）は優先度の高い要素から順に取り出すデータ構造とロジックです。最小値を頂点とする木構造を構築しながら取り出しを行います。

最小値を頂点とする木構造を最小ヒープといいます。最小ヒープを使った場合の優先度とは値の小さいことを意味します。ノードの構築順（挿入順）に関わらず値の小さいノードから優先的に取り出すことができます。

※ダイクストラ法で使用するための「キー減少」は本課題では対応しないとします。

お題のソースコード

最初に下図のようなツリー構造を構築します。すべての子 ≥ 親 を満たしていることがポイントです。

        1
      /   \
     3     10
    /
   5

この二分木構造を１次元配列の数列で表すと下記のようになります。この二分木構造を使って、小さい値から値を取り出すがお題です。

1，3，10，5

ツリー構造への挿入順は下記の想定です。小さい順に挿入していないことがポイントです。

5 → 3 → 10 → 1

Mindの配列の基数は１です。基数０の配列を使った一般的なプログラミング言語の実装とはインデックスの扱いが異なる点にご留意ください。

このあたりとか。

下方へヒープ構築するとは （インデックス　→　・）
  ※～略～
    インデックスに　入れ
    インデックスに　２を　掛けて　インデックス左に　入れ
    インデックス左に　１を　加えて　インデックス右に　入れ
  ※～略～

下記がソースコード全文となります。

priorityqueue.src

最大容量は　        数値　１０。
ヒープは　      最大容量の　変数。
ヒープサイズは　            変数。

最小ヒープを初期化するとは （・　→　・）
    ヒープサイズを　クリアすること。


ヒープ入替するとは （インデックス左　インデックス右　→　・）
        インデックス左は　変数
        インデックス右は　変数
        一時変数は　　　　変数
    
    インデックス右に　入れ
    インデックス左に　入れ
    一時変数に　ヒープ（インデックス左）を　入れ
    ヒープ（インデックス左）に　ヒープ（インデックス右）を　入れ
    ヒープ（インデックス右）に　一時変数を　入れること。


上方へヒープ構築するとは （インデックス　→　・）
        インデックスは　        変数
        親のインデックスは　    変数

    インデックスに　入れ
    インデックスが　１に　等しい　ならば　終わり　つぎに
    インデックスを　２で　割って　親のインデックスに　入れ

    ヒープ（親のインデックス）が　ヒープ（インデックス）より　大きい
    ならば
        親のインデックスと　インデックスを　ヒープ入替し
        親のインデックスで　上方へヒープ構築する
    つぎに。

下方へヒープ構築するとは （インデックス　→　・）
        インデックスは　        変数
        インデックス左は　      変数
        インデックス右は　      変数
        インデックス最小値は    変数
    
    インデックスに　入れ
    インデックスに　２を　掛けて　インデックス左に　入れ
    インデックス左に　１を　加えて　インデックス右に　入れ

    インデックス左が　ヒープサイズより　大きい　ならば　終わり　つぎに
    インデックス最小値に　インデックス左を　入れ

    インデックス右が　ヒープサイズ　以下
    ならば
        ヒープ（インデックス右）が　ヒープ（インデックス左）より　小さい
        ならば
            インデックス最小値に　インデックス右を　入れ
        つぎに
    つぎに

    ヒープ（インデックス）が　ヒープ（インデックス最小値）　以下
    でなければ
        インデックスと　インデックス最小値で　ヒープ入替し
        インデックス最小値で　下方へヒープ構築する
    つぎに。
    
ヒープへ挿入するとは　 （挿入値　→　・）
    ヒープサイズが　最大容量　以上
    ならば　重大エラー　
    つぎに
    ヒープサイズを　一つ増加し
    （挿入値を）　ヒープ（ヒープサイズ）に　入れ
    ヒープサイズで　上方へヒープ構築すること。    

ヒープから最小値を取り出すとは　　（・　→　最小値）
        最小値は　変数

    ヒープサイズが　０に　等しい
    ならば　重大エラー　
    つぎに

    最小値に　ヒープ（１）を　入れ
    ヒープ（１）に　ヒープ（ヒープサイズ）を　入れ
    ヒープサイズを　一つ減少し

    １で　下方へヒープ構築し
    最小値を　返すこと。

ヒープから最小値を参照するとは　　（・　→　最小値）
    ヒープサイズが　０に　等しい
    ならば　重大エラー　
    つぎに
    ヒープ（１）を　返すこと。

ヒープ状態を表示するとは （・　→　・）
    ヒープサイズで　回数指定して
       ヒープ（回数）を　数値表示し　「，」を　表示し
    繰り返す
    改行すること。

メインとは （・　→　・）
    最小ヒープを初期化し

    ５を　ヒープへ挿入し
    ３を　ヒープへ挿入し
    １０を　ヒープへ挿入し
    １を　ヒープへ挿入し
    ヒープ状態を表示する

    ヒープから最小値を参照し　数値表示し　改行し
    ヒープ状態を表示する

    ヒープから最小値を取り出し　数値表示し　改行し
    ヒープ状態を表示する

    ヒープから最小値を取り出し　数値表示し　改行し
    ヒープ状態を表示する

    ヒープから最小値を取り出し　数値表示し　改行し
    ヒープ状態を表示する。

「ヒープへ挿入」という処理単語を数回実行することで最小ヒープを構築しています。値の挿入順は小さい順ではないことがポイントです。

「ヒープから最小値を取り出す」という処理単語で小さい値から取り出しています。

内部的に使っている「下方へヒープ構築する」「上方へヒープ構築する」という処理単語は再帰的に書かれています。

ヒープ配列の「最大容量」はお題の数列の定数配列の要素数より大きめに確保してあります。

お題のソースコードをコンパイル

では、コンパイルしてみます。Mind8によるコンパイル結果です。

C:\developments\vscode\mind9\algorithm>mind priorityqueue file

日本語プログラミング言語 Ｍｉｎｄ Version 8.07 for Windows
          Copyright(C) 1985 Scripts Lab. Inc.
コンパイル中 .. 終了
Coping.. c:\pmind\bin\mindex.exe --> priorityqueue.exe

実行結果

実行結果です。

C:\developments\vscode\mind9\algorithm>priorityqueue
1，3，10，5，
1
1，3，10，5，
1
3，5，10，
3
5，10，
5
10，

相当かなり芸のない出力ですが、小さい値から取り出されていることがわかりますインデックス１のヒープ配列の値を返すわけですが、その際にツリー構造を再構築しているのがポイントです。（数列の変化に注目）

おわりに

いかがでしたでしょうか？わたしはわが国に母語によるプログラミング言語が存在することを誇りに思っております。言語は文化。こんにちの日本語のポップスやアニメソングなどが海外でそのまま歌われるような近況を鑑みますと、純然たる技術基盤として超強力な米欧発プログラミング言語勢と存在意義を争うこともなく、日本語の文化として海外でも日本語プログラミング言語の愛される日が来るのやもしれません。

1. 演算子を被演算子の中間に記述する中置記法 1 + 2、前に記述する前置記法（ポーランド記法）+ 1 2、後に記述する後置記法（逆ポーランド記法）1 2 +がある。日本語は１と ２を 足す。 ↩