検索
ホームページウェブフロントエンドjsチュートリアルヒープのJavaScript実装方法を詳しく解説

ヒープの定義

最大(最小)ヒープは、各ノードのキー値がその子のキー値(存在する場合)以上(より大きい)であるツリーです。大きな上部ヒープは完全なバイナリ ツリーであり、最大ツリーでもあります。ミニヒープは完全なバイナリ ツリーであり、最小ツリーでもあります。

さらに、これら 2 つの概念を覚えておくことはコードを書く上で非常に重要です:

1. 親ノードと子ノードの間の関係: 定義を参照

2. 完全なバイナリ ツリー: [2] を参照

基本操作

1. ビルド (ヒープの構築)

2. 挿入

3. 削除 (削除: 最小または最大のもの)

コードの実装

まず、非常に重要なことが 2 つありますコードを書く前のポイント:

1. 配列はヒープの記憶構造として使用でき、非常にシンプルで操作が簡単です。 2. さらに、配列は記憶構造として使用されるため、親間の関係がわかります。子ノードはインデックスに基づいて簡単に決定できます。

JavaScript の場合、配列インデックスとして 0 から始まる関係は次のとおりです:

nLeftIndex = 2 * (nFatherIndex+1) - 1;
nRightIndex = 2* (nFatherIndex+1);

前述の 2 つの概念を理解すると役立ちます:

1. 配列であるため、その関係親ノードと子ノードの間 特別な構造を維持する必要はなく、インデックス間の計算によって取得できるため、手間が大幅に軽減されます。リンク リスト構造の場合は、さらに複雑になります。

2. 完全なバイナリ ツリーの概念は、次のノードの前に左から右に埋める必要があります。これにより、配列を変更して全体を大きく動かす必要がなくなります。これは、ランダム ストレージ構造 (配列) の欠点でもあります。要素を削除した後、要素全体を前方に移動すると、より時間がかかります。また、この機能により、要素を削除するときにヒープが最後のリーフ ノードをルート ノードに追加します。 コードの実装:

/******************************************************
* file : 堆
* author : "page"
* time : "2016/11/02"
*******************************************************/
function Heap()
{
 this.data = [];
}
 
Heap.prototype.print = function () {
 console.log("Heap: " + this.data);
}
 
Heap.prototype.build = function(data){
 // 初始化
 this.data = [];
 if (!data instanceof Array)
 return false;
 
 // 入堆
 for (var i = 0; i < data.length; ++i) {
 this.insert(data[i]);
 }
 
 return true;
}
 
Heap.prototype.insert = function( nValue ){
 if (!this.data instanceof Array) {
 this.data = [];
 }
 
 this.data.push(nValue);
 // 更新新节点
 var nIndex = this.data.length-1;
 var nFatherIndex = Math.floor((nIndex-1)/2);
 while (nFatherIndex > 0){
 if (this.data[nIndex] < this.data[nFatherIndex]) {
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nFatherIndex];
 this.data[nFatherIndex] = temp;
 }
 
 nIndex = nFatherIndex;
 nFatherIndex = Math.floor((nIndex-1)/2);
 }
}
 
Heap.prototype.delete = function( ){
 if (!this.data instanceof Array) {
 return null;
 }
 
 var nIndex = 0;
 var nValue = this.data[nIndex];
 var nMaxIndex = this.data.length-1;
 // 更新新节点
 var nLeaf = this.data.pop();
 this.data[nIndex] = nLeaf;
 
 while (nIndex < nMaxIndex ){
 var nLeftIndex = 2 * (nIndex+1) - 1;
 var nRightIndex = 2 * (nIndex+1);
 
 // 找最小的一个子节点(nLeftIndex < nRightIndex)
 var nSelectIndex = nLeftIndex;
 if (nRightIndex < nMaxIndex) {
 nSelectIndex = (this.data[nLeftIndex] > this.data[nRightIndex]) ? nRightIndex : nLeftIndex;
 }
 
 if (nSelectIndex < nMaxIndex && this.data[nIndex] > this.data[nSelectIndex] ){
 var temp = this.data[nIndex];
 this.data[nIndex] = this.data[nSelectIndex];
 this.data[nSelectIndex] = temp;
 }
 
 nIndex = nSelectIndex;
 }
 
 return nValue;
}
// test
var heap = new Heap();
heap.build([1, 3, 5, 11, 4, 6, 7, 12, 15, 10, 9, 8]);
heap.print();
// insert
heap.insert(2);
heap.print();
// delete
heap.delete();
heap.print();


JavaScript に関するいくつかの概要を以下に示します。エレガントすぎるように感じます。これより良い表現方法と記述方法があるかどうかはわかりません。

配列の使用法をいくつか学びました。プッシュ操作とポップ操作はとても使いやすいです。も一時的にインターネットから検索されました (instanceof)。これを使用しないと、次回からは忘れてしまうでしょう。

参考


[1]「データ構造とアルゴリズム解析:C言語記述」


[2]グラフィカルデータ構造(8) - バイナリヒープ

[3]>データ構造:ヒープ

まとめ

JavaScript の配列はプッシュおよびポップ操作を実装しており、他の多くの言語でも同様のデータ構造と操作 (C++ の Vector など) が提供されており、ランダム操作もサポートされています。そこで、これらの構造に自動ソートの概念を追加すれば、簡単にヒープを解決できるのではないかと思い始めました。その後、C++ STL の make_heap を見て、自分の知識が少なすぎることに気づきました。私の考え方が正しかったと思います。私は JavaScript を確認しませんでしたが、JavaScript は存在​​するか実装が簡単だと思います。実際に実装してみると、この構造も非常に単純であることがわかりました。一度詳しく触れてみるつもりであれば、


JavaScript の詳細はまだわかっていません。たとえば、JavaScript を使用する前に、配列のアプリケーションについて詳しく読む必要があります。 、そして本質には継続的な学習と練習が必要です

これらのコードは、概念とプログラミングを理解している限り、基本を書き出すことができます。ただし、コードはより簡潔に記述することができます。たとえば、削除関数が最小の子ノードを見つけた場合、左側のノードのインデックスが小さい必要はありません。コード部分は今後も最適化と合理化ができそうな気がします。

声明
この記事の内容はネチズンが自主的に寄稿したものであり、著作権は原著者に帰属します。このサイトは、それに相当する法的責任を負いません。盗作または侵害の疑いのあるコンテンツを見つけた場合は、admin@php.cn までご連絡ください。
Python vs. JavaScript:開発環境とツールPython vs. JavaScript:開発環境とツールApr 26, 2025 am 12:09 AM

開発環境におけるPythonとJavaScriptの両方の選択が重要です。 1)Pythonの開発環境には、Pycharm、Jupyternotebook、Anacondaが含まれます。これらは、データサイエンスと迅速なプロトタイピングに適しています。 2)JavaScriptの開発環境には、フロントエンドおよびバックエンド開発に適したnode.js、vscode、およびwebpackが含まれます。プロジェクトのニーズに応じて適切なツールを選択すると、開発効率とプロジェクトの成功率が向上する可能性があります。

JavaScriptはCで書かれていますか?証拠を調べるJavaScriptはCで書かれていますか?証拠を調べるApr 25, 2025 am 12:15 AM

はい、JavaScriptのエンジンコアはCで記述されています。1)C言語は、JavaScriptエンジンの開発に適した効率的なパフォーマンスと基礎となる制御を提供します。 2)V8エンジンを例にとると、そのコアはCで記述され、Cの効率とオブジェクト指向の特性を組み合わせて書かれています。3)JavaScriptエンジンの作業原理には、解析、コンパイル、実行が含まれ、C言語はこれらのプロセスで重要な役割を果たします。

JavaScriptの役割:WebをインタラクティブでダイナミックにするJavaScriptの役割:WebをインタラクティブでダイナミックにするApr 24, 2025 am 12:12 AM

JavaScriptは、Webページのインタラクティブ性とダイナミズムを向上させるため、現代のWebサイトの中心にあります。 1)ページを更新せずにコンテンツを変更できます。2)Domapiを介してWebページを操作する、3)アニメーションやドラッグアンドドロップなどの複雑なインタラクティブ効果、4)ユーザーエクスペリエンスを改善するためのパフォーマンスとベストプラクティスを最適化します。

CおよびJavaScript:接続が説明しましたCおよびJavaScript:接続が説明しましたApr 23, 2025 am 12:07 AM

CおよびJavaScriptは、WebAssemblyを介して相互運用性を実現します。 1)CコードはWebAssemblyモジュールにコンパイルされ、JavaScript環境に導入され、コンピューティングパワーが強化されます。 2)ゲーム開発では、Cは物理エンジンとグラフィックスレンダリングを処理し、JavaScriptはゲームロジックとユーザーインターフェイスを担当します。

Webサイトからアプリまで:JavaScriptの多様なアプリケーションWebサイトからアプリまで:JavaScriptの多様なアプリケーションApr 22, 2025 am 12:02 AM

JavaScriptは、Webサイト、モバイルアプリケーション、デスクトップアプリケーション、サーバー側のプログラミングで広く使用されています。 1)Webサイト開発では、JavaScriptはHTMLおよびCSSと一緒にDOMを運用して、JQueryやReactなどのフレームワークをサポートします。 2)ReactNativeおよびIonicを通じて、JavaScriptはクロスプラットフォームモバイルアプリケーションを開発するために使用されます。 3)電子フレームワークにより、JavaScriptはデスクトップアプリケーションを構築できます。 4)node.jsを使用すると、JavaScriptがサーバー側で実行され、高い並行リクエストをサポートします。

Python vs. JavaScript:ユースケースとアプリケーションと比較されますPython vs. JavaScript:ユースケースとアプリケーションと比較されますApr 21, 2025 am 12:01 AM

Pythonはデータサイエンスと自動化により適していますが、JavaScriptはフロントエンドとフルスタックの開発により適しています。 1. Pythonは、データ処理とモデリングのためにNumpyやPandasなどのライブラリを使用して、データサイエンスと機械学習でうまく機能します。 2。Pythonは、自動化とスクリプトにおいて簡潔で効率的です。 3. JavaScriptはフロントエンド開発に不可欠であり、動的なWebページと単一ページアプリケーションの構築に使用されます。 4. JavaScriptは、node.jsを通じてバックエンド開発において役割を果たし、フルスタック開発をサポートします。

JavaScript通訳者とコンパイラにおけるC/Cの役割JavaScript通訳者とコンパイラにおけるC/Cの役割Apr 20, 2025 am 12:01 AM

CとCは、主に通訳者とJITコンパイラを実装するために使用されるJavaScriptエンジンで重要な役割を果たします。 1)cは、JavaScriptソースコードを解析し、抽象的な構文ツリーを生成するために使用されます。 2)Cは、Bytecodeの生成と実行を担当します。 3)Cは、JITコンパイラを実装し、実行時にホットスポットコードを最適化およびコンパイルし、JavaScriptの実行効率を大幅に改善します。

JavaScript in Action:実際の例とプロジェクトJavaScript in Action:実際の例とプロジェクトApr 19, 2025 am 12:13 AM

現実世界でのJavaScriptのアプリケーションには、フロントエンドとバックエンドの開発が含まれます。 1)DOM操作とイベント処理を含むTODOリストアプリケーションを構築して、フロントエンドアプリケーションを表示します。 2)node.jsを介してRestfulapiを構築し、バックエンドアプリケーションをデモンストレーションします。

See all articles

ホットAIツール

Undresser.AI Undress

Undresser.AI Undress

リアルなヌード写真を作成する AI 搭載アプリ

AI Clothes Remover

AI Clothes Remover

写真から衣服を削除するオンライン AI ツール。

Undress AI Tool

Undress AI Tool

脱衣画像を無料で

Clothoff.io

Clothoff.io

AI衣類リムーバー

Video Face Swap

Video Face Swap

完全無料の AI 顔交換ツールを使用して、あらゆるビデオの顔を簡単に交換できます。

ホットツール

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Eclipse を SAP NetWeaver アプリケーション サーバーと統合します。

AtomエディタMac版ダウンロード

AtomエディタMac版ダウンロード

最も人気のあるオープンソースエディター

EditPlus 中国語クラック版

EditPlus 中国語クラック版

サイズが小さく、構文の強調表示、コード プロンプト機能はサポートされていません

SublimeText3 英語版

SublimeText3 英語版

推奨: Win バージョン、コードプロンプトをサポート!

MantisBT

MantisBT

Mantis は、製品の欠陥追跡を支援するために設計された、導入が簡単な Web ベースの欠陥追跡ツールです。 PHP、MySQL、Web サーバーが必要です。デモおよびホスティング サービスをチェックしてください。