GinO | ページ 15

[データ構造] 2分ヒープをPythonで実装

Python のリストを使い Max Heap を2分ヒープで実装します。初期化配列の最大要素数を定数MAX_NUM_ITEMSとして定めます。また、self.heap_size という定数を用意して、配列の最後の要素にアクセスする際...

ヒープは過去にもまとめています。最初よく混乱しますが、メモリのヒープとデータ構造のヒープは別のものです。 2分ヒープ二分ヒープ（にぶんヒープ,バイナリヒープ,Binary heap）とは、二分木を使って作られるヒープ(データ...

優先度付きキュー優先度付きキュー（ゆうせんどつき -、英:priority queue）は、以下の4つの操作をサポートする抽象データ型である。キューに対して要素を優先度付きで追加する。最も高い優先度を持つ要素をキューから取り除き、それを返す。(オプ...

以前にまとめた赤黒木は以下です。赤黒木 Red Black Tree 赤黒木（あかくろぎ）は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。2色木、レッド・ブラック・ツリーともいう。出...

Python でAVL木を実装します。ノード 2分探索木とあまり変わりません。 height というインスタンス変数を設定し、ノードの高さを保持します。 class Node(object): def __init__(s...

平衡二分探索木平衡二分探索木（へいこうにぶんたんさくぎ、英:self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（平衡木...

2分探索木を Python で実装します。以前、ほぼ全く同じ内容で記事を書いています。ノード 2分探索木では、ノードは自身のデータと、0個、1個、2個のいずれかの子ノードを持っており、左側の子ノードは親の値より小さい値、右...

二分探索木二分探索木（にぶんたんさくぎ、英:binary search tree）は、コンピュータプログラムにおいて、「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」という制約を持つ二分木である。探索木のうちで最も基本的な木構造である。出典: フリ...

キューキュー（英: queue）、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出しのリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れること...

スタックスタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out;FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこ...