C LANGUAGE TECHNOLOGY

【C言語】キューとは【優先度キューの二項ヒープを紹介】

悩んでいる人

C言語のキューを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

キュー

キューとは,データを先入れ先出し(First In First Out)で保持するデータ構造です.

キューにデータに入れることをエンキュー(enqueue),データをキューから取り出すことをデキュー(dequeue)と呼びます.

他のデータ構造を知りたいあなたはこちらからどうぞ.

C言語 リスト
【C言語】連結リストとは【片方向リスト,双方向リスト,双方向循環リスト】

こういった悩みにお答えします. こういった私から学べます. 目次1 連結リスト2 C言語のリスト2.1 片方向リスト2.2 双方向リスト2.3 双方向循環リスト3 リストの実例:Linuxカーネル3. ...

続きを見る

C言語 スタック
【C言語】スタックとは【x86のアセンブリ言語で解説】

こういった悩みにお答えします. こういった私から学べます. 目次1 スタック2 C言語のスタック3 x86の命令セットアーキテクチャでスタックを操作するpush/pop命令4 まとめ スタック スタッ ...

続きを見る

C言語のキュー

C言語のシンプルなキューのコードは以下になります.

QUEUE_SIZE分のデータを格納できます.

実行結果は以下になります.

データをFIFOで操作していることがわかります.

C言語の優先度キューの例「二項ヒープ」

キューの応用として,データを優先度付きで管理する優先度キューが挙げられます.

優先度キューでは,主に最高優先度のデータをキューから取り除くため,リアルタイムOSにおけるタスクのキューで利用されています.

優先度キューにより,リアルタイム性を保証しつつタスクをデッドラインまでに実行することが可能になります.

リアルタイムOSに使われる技術であるリアルタイムシステムを知りたいあなたはこちらからどうぞ.

リアルタイムシステム
元東大教員から学ぶリアルタイムシステム

こういった私から学べます. リアルタイムシステムとは,決められた時間(デッドライン)までに処理を完了しなければならない性質をもつシステムのことです. リアルタイムシステムは,ロボット,自動車や航空機な ...

続きを見る

本記事では,優先度キューの例として二項ヒープを紹介します.

二項ヒープの特徴は以下になります.

  • 二分ヒープとよく似たデータ構造であるが,二項ヒープは2つのヒープを素早くマージする操作をサポート
  • 特殊な木構造「二項木」を利用して実現
  • マージ可能な抽象データ型ヒープの実装

C言語の二項ヒープのコードは以下になります.

とても複雑なので,時間をかけて読みましょう.難しかったら読み飛ばしても構いません.

二項ヒープのコードで実装されている主な関数は以下になります.

  • enqueue_bheap_queue関数:二項ヒープにノードをエンキュー
  • dequeue_bheap_queue関数:二項ヒープからノードをデキュー
  • pick_next_value関数:二項ヒープから最高優先度ノードの値(struct value型)を取得
  • print_bheap関数:二項ヒープのノードを表示

実行結果は以下になります.

enqueue_bheap_queue関数でノードをエンキューしたり,dequeue_bheap_queue関数でノードをデキューしたりした場合に,二項ヒープの木構造がどのように変化するのかをprint_bheap関数で確認しています.

最高優先度ノードの値を取得したい場合は,pick_next_value関数を利用します.

ここで,pick_next_value関数では,ノードをデキューしないことに注意して下さい.

まとめ

C言語のキューとして,シンプルなキューと,優先度キューの二項ヒープを紹介しました.

二項ヒープのコードは複雑なので,コードを修正したらどのように結果が変化するのかを試してみましょう.

他のキューとしてリングバッファ(リングキュー)が挙げられます.

C言語のリングバッファのコードを知りたいあなたはこちらからどうぞ.

C言語 リングバッファ
【C言語】おすすめのリングバッファのライブラリ

こういった悩みにお答えします. こういった私から学べます. 目次1 embedded-resources:おすすめのリングバッファのライブラリ2 embedded-resourcesのC言語のリングバ ...

続きを見る

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

友だち追加

独学が難しいあなたは,C言語を学べるおすすめのオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , ,