[データ構造] 2分ヒープをPythonで実装
Python のリストを使い Max Heap を2分ヒープで実装します。 初期化 配列の最大要素数を定数MAX_NUM_ITEMSとして定めます。 また、self.heap_size という定数を用意して、配列の最後の要素にアクセスする際...
[データ構造] ヒープ
ヒープは過去にもまとめています。 最初よく混乱しますが、メモリのヒープとデータ構造のヒープは別のものです。 2分ヒープ 二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ...
[データ構造] 優先度付きキュー
優先度付きキュー 優先度付きキュー（ゆうせんどつき -、英:priority queue）は、以下の4つの操作をサポートする抽象データ型である。 キューに対して要素を優先度付きで追加する。最も高い優先度を持つ要素をキューから取り除き、それを返す。(オプ...
[データ構造] 赤黒木
以前にまとめた赤黒木は以下です。 赤黒木 Red Black Tree 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。 出...
[データ構造] AVL木を Python で実装
Python でAVL木を実装します。 ノード 2分探索木とあまり変わりません。 height というインスタンス変数を設定し、ノードの高さを保持します。 class Node(object): def __init__(s...
[データ構造] AVL木
平衡二分探索木 平衡二分探索木（へいこうにぶんたんさくぎ、英:self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木...
[データ構造] 2分探索木の Python での実装
2分探索木を Python で実装します。 以前、ほぼ全く同じ内容で記事を書いています。 ノード 2分探索木では、ノードは自身のデータと、0個、1個、2個のいずれかの子ノードを持っており、左側の子ノードは親の値より小さい値、右...
[データ構造] 2分探索木
二分探索木 二分探索木（にぶんたんさくぎ、英:binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。 出典: フリ...
[データ構造] キュー
キュー キュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出しのリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れること...
[データ構造] スタック
スタック スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out;FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこ...