データ構造の優先キュー：特性、タイプ、および実装

公開: 2021-05-02

目次

序章

データ構造の優先キューは、「通常の」キューの拡張です。 これは、アイテムのグループを含む抽象データ型です。 デキュー要素が優先順位に従うことを除けば、「通常の」キューに似ています。 優先順位は、優先度が最も高いアイテムを最初にデキューします。 このブログでは、優先度付きキューとそのCプログラミング言語での実装について深く理解することができます。

優先キューとは何ですか？

これは、データセットを維持する方法を提供する抽象データ型です。 「通常の」キューは、先入れ先出しのパターンに従います。 挿入操作時と同じ順序で要素をデキューします。 ただし、優先キュー内の要素の順序は、そのキュー内の要素の優先度によって異なります。 優先度キューは、優先度キューの先頭にある最も高い優先度の要素と、優先度付きキューの後ろにある最も低い優先度の要素を移動します。

比較可能な要素のみをサポートします。 したがって、データ構造の優先キューは、要素を昇順または降順で配置します。

優先キューは、病院で並んで待っている数人の患者と考えることができます。 ここでは、患者の状況が優先順位を定義します。 最も重傷を負った患者が最初に列に並びます。

優先キューの特徴は何ですか？

キューに次の特性がある場合、キューは優先キューと呼ばれます。

  • 各アイテムには、いくつかの優先順位が関連付けられています。
  • 優先度が最も高いアイテムが先頭に移動され、最初に削除されます。
  • 2つの要素が同じ優先度値を共有する場合、優先度キューは、デキュー操作の先入れ先出しの原則に従います。

優先キューの種類は何ですか？

優先キューには次の2つのタイプがあります。

  • 昇順優先キュー
  • 降順優先キュー

昇順優先キュー

昇順の優先度キューは、そのキュー内の小さい番号に最高の優先度を与えます。 たとえば、優先キューには4、8、12、45、35、20の6つの番号があります。最初に、これらの番号を昇順で並べます。 新しいリストは次のとおりです。4、8、12、20。35、45。このリストでは、4が最小の番号です。 したがって、昇順優先キューは番号4を最高の優先度として扱います。

4 8 12 20 35 45

上記の表では、4が最高の優先度で、45が最低の優先度です。

降順優先キュー

降順の優先度キューは、そのキュー内の最大番号に最高の優先度を与えます。 たとえば、優先キューには4、8、12、45、35、20の6つの番号があります。最初に、これらの番号を昇順で並べます。 新しいリストは次のとおりです。45、35、20、12、8、4。このリストでは、45が最大の番号です。 したがって、降順の優先度キューは、番号45を最高の優先度として扱います。

45 35 20 12 8 4

上記の表では、4が最低の優先度で、45が最高の優先度です。

データ構造での優先キューの実装

優先キューは、次のいずれかの方法で実装できます。

  • リンクリスト
  • バイナリヒープ
  • 配列
  • 二分探索木

バイナリヒープは、データ構造に優先度付きキューを実装するための最も効率的な方法です。

次の表は、優先キューでのさまざまな操作の複雑さをまとめたものです。

手術順序付けられていない配列順序付き配列バイナリヒープ二分探索木
入れる0（1） 0（N） 0（log（N）） 0（log（N））
ピーク0（N） 0（1） 0（1） 0（1）
消去0（N） 0（1） 0（ログ（N）） 0（log（N））

バイナリヒープ

バイナリヒープツリーは、ツリーのすべての親ノードと子ノードを特定の順序で編成します。 バイナリヒープツリーでは、親ノードは最大2つの子ノードを持つことができます。 親ノードの値は次のいずれかになります。

  • 子ノードの値以下。
  • 子ノードの値以上。

上記のプロセスは、バイナリヒープを最大ヒープと最小ヒープの2つのタイプに分割します。

最大ヒープ

最大ヒープは、親ノードの値が子ノードの値以上のバイナリヒープです。 ツリーのルートノードの値が最も高くなります。

最大ヒープバイナリツリーへの要素の挿入

次の手順を実行して、データ構造の優先キューに要素/番号を挿入できます。

  1. アルゴリズムはツリーを上から下、左から右にスキャンして空のスロットを見つけます。 次に、ツリーの最後のノードに要素を挿入します。
  2. 要素を挿入した後、二分木の順序が乱れます。 最大ヒープバイナリツリーの順序を並べ替えるには、データを相互に交換する必要があります。 ツリーがmax-heapプロパティを満たすまで、データをシャッフルし続ける必要があります。

最大ヒープ二分木に要素を挿入するアルゴリズム

ツリーが空でノードが含まれていない場合、

新しい親ノードnewElementを作成します。

else（親ノードはすでに使用可能です）

ツリーの最後にnewElementを挿入します（つまり、ツリーの最後のノードを左から右に）。

max-ツリーをヒープ化します

最大ヒープバイナリツリーの要素を削除する

  1. 次の手順を実行して、データ構造の優先キューの要素を削除できます。
  2. バイナリツリーから削除する要素を選択します。
  3. ツリーの最後にあるデータを最後のノードデータと交換してシフトします。
  4. 二分木の最後の要素を削除します。
  5. 要素を削除すると、二分木の順序が乱れます。 max-heapのプロパティを満たすには、順序を並べ替える必要があります。 ツリーがmax-heapプロパティを満たすまで、データをシャッフルし続ける必要があります。

最大ヒープバイナリツリーの要素を削除するアルゴリズム

elementUpForDeletionがlastNodeの場合、

elementUpForDeletionを削除します

それ以外の場合は、elementUpForDeletionをlastNodeに置き換えます

elementUpForDeletionを削除します

max-ツリーをヒープ化します

最大ヒープバイナリツリーで最大要素または最小要素を見つける

最大ヒープバイナリツリーでは、find操作はツリーの親ノード（最上位の要素）を返します。

最大ヒープバイナリツリーで最大または最小を見つけるアルゴリズム

ParentNodeを返す

最大ヒープ二分木を使用した優先キューのプログラム実装

#include <stdio.h>

int binary_tree = 10;

int max_heap = 0;

const int test = 100000;

void swap（int * x、int * y）{

int a;

a = * x;

* x = * y;

* y = a;

}

//最大ヒープツリーで親を見つけるためのコード

int findParentNode（int node []、int root）{

if（（root> 1）&&（root <binary_tree））{

ルート/2を返します。

}

-1を返します。

}

void max_heapify（int node []、int root）{

int leftNodeRoot = findLeftChild（node、root）;

int rightNodeRoot = findRightChild（node、root）;

//ルート、左の子、右の子の中で最も高いものを見つける

inthighest=ルート;

if（（leftNodeRoot <= max_heap）&&（leftNodeRoot> 0））{

if（node [leftNodeRoot]> node [highest]）{

最高=leftNodeRoot;

}

}

if（（rightNodeRoot <= max_heap）&&（rightNodeRoot> 0））{

if（node [rightNodeRoot]> node [highest]）{

最高=rightNodeRoot;

}

}

if（highest！= root）{

swap（＆node [root]、＆node [highest]）;

max_heapify（node、highest）;

}

}

void create_max_heap（int node []）{

int d;

for（d = max_heap / 2; d> = 1; d–）{

max_heapify（node、d）;

}

}

int maximum（int node []）{

リターンノード[1];

}

int find_max（int node []）{

int maxNode = node [1];

node [1] = node [max_heap];

max_heap–;

max_heapify（node、1）;

maxNodeを返します。

}

voiddescend_key（int node []、int node、int key）{

A[ルート]=キー;

max_heapify（node、root）;

}

ボイドincrease_key（int node []、int root、int key）{

node[root]=キー;

while（（root> 1）&&（node [findParentNode（node、root）] <node [root]））{

swap（＆node [root]、＆node [findParentNode（node、root）]）;

root = findParentNode（node、root）;

}

}

void insert（int node []、int key）{

max_heap ++;

node [max_heap] = -1 * test;

増加キー（ノード、最大ヒープ、キー）;

}

void display_heap（int node []）{

int d;

for（d = 1; d <= max_heap; d ++）{

printf（“％d \ n”、node [d]）;

}

printf（“ \ n”）;

}

int main（）{

int node [binary_tree];

insert（node、10）;

insert（node、4）;

insert（node、20）;

insert（node、50）;

insert（node、1）;

insert（node、15）;

display_heap（node）;

printf（“％d \ n \ n”、maximum（node））;

display_heap（node）;

printf（“％d \ n”、extract_max（node））;

printf（“％d \ n”、extract_max（node））;

0を返します。

}

最小ヒープ

min-heapは、親ノードの値が子ノードの値以下のバイナリヒープです。 ツリーのルートノードの値が最も低くなります。

順序を逆にすることを除いて、最大ヒープと同じ方法で最小ヒープを実装できます。

結論

この記事に記載されている例は、説明のみを目的としています。 要件に応じて、上記のステートメントを変更できます。 このブログでは、データ構造の優先キューの概念について学びました。 この例を試して、データ構造の知識を強化することができます。

データサイエンスについて知りたい場合は、IIIT-B＆upGradのデータサイエンスのエグゼクティブPGプログラムをチェックしてください。これは、働く専門家向けに作成され、10以上のケーススタディとプロジェクト、実践的なハンズオンワークショップ、業界の専門家とのメンターシップを提供します。1業界のメンターとの1対1、400時間以上の学習、トップ企業との仕事の支援。

世界のトップ大学からオンラインでデータサイエンスコースを学びましょう。 エグゼクティブPGプログラム、高度な証明書プログラム、または修士プログラムを取得して、キャリアを早急に進めましょう。

優先キューのアプリケーションは何ですか？

優先度付きキューは、要素が優先度に基づいて挿入される特別なキューです。 この機能は、他のさまざまなデータ構造の実装に役立ちます。 以下は、優先キューの最も一般的なアプリケーションの一部です。
 1.ダイクストラの最短経路アルゴリズム：グラフが隣接リストの形式で保存されている場合、ダイクストラの最短経路アルゴリズムで優先キューを使用できます。
 2.プリムのアルゴリズム：プリムのアルゴリズムは、ノードの値またはキーに対して優先度キューを使用し、すべてのステップでこれらの値の最小値を引き出します。
 データ圧縮：ハフマンコードは優先キューを使用してデータを圧縮します。
 オペレーティングシステム：優先キューは、負荷分散や割り込み処理などのさまざまなプロセスのオペレーティングシステムに非常に役立ちます。

アレイを使用した優先キューの実装では、どのようなアプローチが使用されますか？

配列を使用した優先キューの実装で使用されるアプローチは単純です。 要素の値と優先度を格納するために構造が作成され、次にその構造の配列が作成されて要素が格納されます。 この実装には、次の操作が含まれます。
 1. enqueue（）-この関数は、キューの最後に要素を挿入します。
 2. peek（）-この関数は配列をトラバースして、最も優先度の高い要素を返します。 同じ優先度を持つ2つの要素が見つかった場合、それらの中で最も高い値の要素を返します。
 3. dequeue（）-この関数は、すべての要素をシフトします。peek（）関数によって返される要素の1つ左に位置し、サイズを小さくします。

最大ヒープと最小ヒープの違いは何ですか？

以下は、最大ヒープと最小ヒープの違いを示しています。
 最小ヒープ-最小ヒープでは、ルートノードのキーはその子ノードのキー以下である必要があります。 昇順の優先順位を使用します。 キーが最小のノードが優先されます。 最小の要素が他の要素の前にポップされます。
 最大ヒープ-最大ヒープでは、ルートノードのキーはその子ノードのキー以上である必要があります。 降順の優先度を使用します。 キーが最大のノードが優先されます。 最大の要素が他の要素の前にポップされます。