アルゴリズムとデータ構造 - ヒープソート
2020年2月1日概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープソート 要素の並べ替えを二分ヒープ木を用いて行うソート ヒープの構築 ヒープから要素（根）を取り出す操作をヒープ木が空になるまで行う 計算時間 最悪計算時間、平均計算時間 O(n log n) 実装package...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープソート 要素の並べ替えを二分ヒープ木を用いて行うソート ヒープの構築 ヒープから要素（根）を取り出す操作をヒープ木が空になるまで行う 計算時間 最悪計算時間、平均計算時間 O(n log n) 実装package...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 挿入ソート データ列の先頭から順番にソートしていく ソート済みと未ソートでそれぞれ部分列に分けられる 1回目：0番目をソート済みとするので何もしない 2回目：0番目と1番目を比較して順序が逆なら入れ変える 3回目：0番目から1番目...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 選択ソート データを昇順または降順に並べ変えるソートの一つ １番目の要素と2番目以降の要素の中で最小の値を比較して、順序が逆なら入れ変えを行う、という操作をデータ列の最後の一つ手前まで繰り返す 計算時間 最良計算時間、平均計算時...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 バブルソート データを昇順または降順に並べ変えるソートの一つ 全要素に対して、隣合う要素同士を比較し、順序が逆なら入れ替えを行う、という操作を要素数-1回繰り返す 計算時間 最悪計算時間、最良計算時間、平均計算時間 O(n²) ...
概要 GolangでURLルーターを自作したので実装するまでの過程をメモしておく。 準備 URLルーターを実装する際に行った下準備をまとめる。 データ構造とアルゴリズム URLをどのようにマッチングさせるか、というロジックについて検討する。 多くのライブラリでは、データ構造として木構造がよく扱われているので、どんな種類の木構造を採用するかを考えてみた。 文字列探索に特化した木の中で、時間的・メモリ...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 二分探索木 各ノードが多くとも2つまでのノードしか持たない二分木の一種で、左の子ノード ≤ 親 ≤ 右の子ノードという制約を持った構造の木 最も左にあるノードが最小ノードで、最も右にあるノードが最大ノードとなる 二分探索木に限...
概要アルゴリズム図鑑を参考に、アルゴリズムとデータ構造を学ぶ。 実装はgithub - bmf-san/road-to-algorithm-masterにも置いてある。 ヒープ 優先度付きキュー（priority queue）の一種 優先度付きキューは、集合（set）を扱うデータ型 集合に含まれる要素は優先度順に取り出される 集合を扱うデータ型の例：キュー、スタック ヒープの種類 ...
2019年の振り返りと来年の抱負今年も残すところ1週間とちょっとくらいになったので、今年の振り返りと来年の抱負をポエムっとく。 今年の振り返りここ3年間くらい右肩上がりで公私ともに良い機会、良い経験に恵まれている。今年は特に良い年だったと思う。めんどくさいので雑に箇条書きにしていく。 パブリックな方面個別の事柄をピックアップして書きたいけど、多すぎて大変面倒なことになるので総括だけ。 リードエン...
概要 この記事はURLルーティング自作入門 エピソード１の続きで、Makuake Development Team Advent Calendar 2019の15日目となります。 URLルーティングを自作する 前回の続きです。 ルーターを自作するにあたり、ルーターがどういった処理を行うのかデータ構造の観点から考えてみます。 ルーターがどんなInputを受け取って、どんなOutputを返すのか、動...
概要 この記事はMakuake Development Team Advent Calendar 2019の14日目の記事です。 趣味で駆け出し※URLルーティング自作マンをやっているので、URLルーティング自作界隈※に入門したい人に向けた記事となれば幸いです。 ※駆け出しというキーワードが今年はWeb界隈で流行り？ましたね。私は去年末からURLルーティング自作を始めたので駆け出しだと思います。 ...