
JavaScriptで優先度付きキューを実装する
2021-08-016 min read
目次
概要
JavaScriptで優先度付きキュー (プライオリティキュー) を実装する
優先度付きキューについて
具体的には次のような機能があります。
- キューに対して要素を優先度付きで追加 (push)
- 最も高い優先度を持つ要素をキューから取り除きそれを返す (pop)
ソース
/**
* 優先度付きキュー
*/
class priorityQueue {
/**
* コンストラクタ
*/
constructor() {
this.a = []
}
/**
* キューに値を追加する
*
* @param x
*/
push(x) {
const a = this.a;
for (var i = a.length, j; i; i = j) {
j = i - 1 >> 1
if (a[j] <= x) {
break
}
a[i] = a[j]
}
a[i] = x
}
/**
* キューから値を取り出す
*
* @returns
*/
pop() {
const a = this.a
const r = a[0]
const x = a.pop()
const k = a.length >> 1;
for (var i = 0, j; i < k; i = j) {
j = (i << 1) + 1
if (a[j + 1] < a[j]) {
j++
}
if (x <= a[j]) {
break
}
a[i] = a[j]
}
if (a.length) {
a[i] = x
}
return r
}
/**
* サイズを取得
*
* @returns 長さ
*/
size() {
return this.a.length
}
/**
* 最も高い優先度を持つ要素を取り除くことなく参照する
*
* @returns
*/
top() {
return this.a[0]
}
}
参考
優先度付きキュー(PriorityQueue)っぽいものをJSで実装する
FastPriorityQueue.js : a fast, heap-based priority queue in JavaScript
Recommends
JavaScriptで優先度付きキューを実装する
2021-08-01
next_permutationをJSで実装する
2021-07-22
javascriptで累積和を解く
2022-02-27
JSで動的計画法を利用して部分和問題を解く
2022-02-20
10進数から2進数 2進数から10進数への変換 JavaScript
2020-07-12
JavaScriptの配列ショートハンド (AtCoder用)
2020-07-05
JavaScriptでワーシャルフロイド法を実装
2020-06-21
JavaScriptによる2分探索(バイナリサーチ) のサンプルコード
2020-05-24
JavaScriptで幅優先探索 (bfs) を実装する
2020-01-13
順列・組み合わせ のサンプルコード JS [permutation] [combina...
2019-06-30
JavaScript で bit全探索
2019-06-10
深さ優先探索アルゴリズムを実装 部分和問題を解く
2018-12-25
複数キーでソートするサンプルコード JavaScript
2018-11-05
GatsbyからNext.jsへのサイト移行
2022-04-04
NextJSでDevToysのようなものを作成した
2022-02-22
New Posts
[CDK]SNS+SQS+DynamoDBでBounceとComplaint情報を収集する...
2022-04-11
[AmazonSES] node.js と ejs を利用してEメールを送信する
2022-04-09
GatsbyからNext.jsへのサイト移行
2022-04-04
[AWS CDK] Lambda で S3 オブジェクトを読み書きするStackの構築
2022-03-18
[AWS CDK] S3 + CloudFrontの構築とOriginAccessIden...
2022-03-09
[AWS CDK] Bastion(踏み台)構築。SSMとEC2InstanceConne...
2022-03-06
[AWS CDK] Cognito を構築
2022-03-04
AWS CDK v2 でVPC上にAPI Gateway + Lambda + RDS +...
2022-02-28
javascriptで累積和を解く
2022-02-27
AWS Amplify で monorepo を導入し 単一リポジトリで複数プロジェクトを...
2022-02-25
AWS CDK v2 で Lambda関数のデプロイ
2022-02-23
NextJSでDevToysのようなものを作成した
2022-02-22
JSで動的計画法を利用して部分和問題を解く
2022-02-20
NestJSアプリケーションをwebpackでBundle
2022-02-20
[Next.js] Warning: Assign arrow function to a...
2022-02-13
Hot posts!
Proxy環境下でcurlを実行する
2019-12-07
OpenCVのMatのタイプ一覧表
2018-11-25
Macでも利用できるDBクライアント MySQL PostgreSQL Oracle など
2019-12-21
TablePlusを使ってみる。シンプルでモダンなSQLクライアントツール
2018-09-30
DBクライアントツールはDBeaverをおすすめしたい
2021-03-08
AWS S3のアクセスキーIDとシークレットアクセスキーの取得 作業用ユーザを作成
2019-06-12
AtCoderで初めて色がつくまでの話(茶色) レートが中々上がらなかった原因
2018-11-25
CentOS8でEPELとPowerToolsリポジトリの有効化
2020-11-30
Macでターミナルからポートスキャンを行う方法。
2018-12-09
Python + OpenCVのfillConvexPolyで複雑なポリゴンを描画する
2018-11-27
Date
▶︎
2022 年 (21)
▶︎
2021 年 (40)
▶︎
2020 年 (30)
▶︎
2019 年 (90)
▶︎
2018 年 (89)
▶︎
2017 年 (1)
Tags
Author