Binomial heap - Wikipedia
In computer science, a binomial heap is a data structure that acts as a priority queue. It is an example of a mergeable heap (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a heap similar to a binary heap but using a special tree structure that is different from the complete binary trees used by binary heaps.[1] Binomial heaps were invented i
優先度付き待ち行列(アルゴリズムとデータ構造)
概要 優先度付き待ち行列（priority queue）とは、 ある優先度（例えば、値の大きな物ほど優先度が高いとか）に従って、 優先度の高いものから順に取り出すことの出来るコレクションです。 挿入順序がどうであれ、優先度の高いものが必ず1番最初に取り出されます。 優先度付き待ち行列 名前に「待ち行列」という言葉が含まれていることから分かるように、 優先度付き待ち行列への値の挿入・取り出しはそれぞれエンキュー・デキューといいます。 「待ち行列」のときと同様に、 「スタック」と呼び名をそろえるために、 プッシュ・ポップという名前で実装する場合もあります。 このようなコレクションを実現するためには、 例えば、ソート済みの配列を使うといった方法も考えられますが、 優先度が1番高い要素1つだけが分かれば十分なのに、 ソートを行うのでは余分な労力を裂いていることになります。 これに対して、 優先度が
ヒープ
最近の主な更新 2006-05-21 - 第二版 2001-xx-xx - 初版 はじめに int 型の配列が与えられたとする．この配列から，値の大きい順で要素を取り 出したい．しかもできるだけ効率的に．どうすればよいだろうか． このような問題を解くためのデータ構造が，ヒープである． ヒープの解説に入る前に，まず，上の問題に対する単純な解法を考えてみる． おそらく，次のような方法が思いつくはずである．配列の要素を前から順に見 ていく．このとき，現在の最大値を格納する要素の添字を覚えておく．配列の 最後の要素まで到達したら，覚えておいた添字の場所にある要素を取り出す． これを，配列が空になるまで繰り返す． この方法では，配列の大きさを n としたとき，(n-1) + (n-2) + ... + 1 = n(n-1)/2 回の比較を必要とする．従って，計算量としてはO(n^2)のアルゴリ ズム
ヒープソート - Wikipedia
ヒープソート (heap sort) とはリストの並べ替えを二分ヒープ木を用いて行うソートのアルゴリズムである[2]（ヒープ領域とは無関係であることに注意する）。 アルゴリズムは、以下のように2つの段階から構成される。 未整列のリストから要素を取り出し、順にヒープに追加する。すべての要素を追加するまで繰り返し。 ルート（最大値または最小値)を取り出し、整列済みリストに追加する。すべての要素を取り出すまで繰り返し。 計算量は O となる[2]。安定ソートではない[2]。 アルゴリズム[編集] ヒープ構造は、ポインタ等の制御用データが不要で、データ自体の並び順（配列）だけで表現できるという利点がある。ヒープソートを実装する際にはこの利点を生かし、元のデータ領域をそのままヒープ構造や整列済みリストに転用するインプレースなソートとして実装することが多い。 最初にN個のデータを含む配列が与えられるも
ヒープ : データ構造
ヒープは半順序集合をツリーで表現したデータ構造です。親ノードは、子ノードよりも小さい(あるいは大きい)か等しいという条件を満たすツリー構造になります。子の関係に制約はありません。あくまで親子間での制約です。 単にヒープと呼ぶ場合、バイナリツリーとして構成されるバイナリヒープを指すことが多いです。 Infoコンピュータ サイエンスでヒープと言う場合「ヒープ領域」を指すこともありますので間違わないようにしましょう。 特徴 - ヒープ プロパティ 親子の関係によってヒープの性質 - ヒープ プロパティ [heap property] は2種類に分かれます。 最大ヒープ [max-heap property] 親ノードは子ノードより大きいか等しい。 最小ヒープ [min-heap property] 親ノードは子ノードより小さいか等しい。 プロパティによりルートノードは常に最大あるいは最小要素とな
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
データ構造とアルゴリズム: ヒープとヒープソート
Binomial Heap
programming methodology
Top Ten Tags
