資訊專欄INFORMATION COLUMN
摘要：堆的算法優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，最重要的操作是刪除最大元素和插入元素。用長度為的數(shù)組來表示一個大小為的堆，堆元素放在至中，不使用。由下至上的堆有序化上浮的實(shí)現(xiàn)由上至下的堆有序化下沉的實(shí)現(xiàn)堆實(shí)現(xiàn)的比較和交換方法
堆的算法
優(yōu)先隊(duì)列是一種抽象數(shù)據(jù)類型，最重要的操作是刪除最大元素和插入元素。
用長度為N+1的數(shù)組pq[]來表示一個大小為N的堆，堆元素放在pq[1]至pq[N]中，不使用pq[0]。
function MaxPQ(){
var pq = [],
n = 0;
this.show = function(){
console.log(pq);
}
this.insert = function(v){
pq[++n] = v;
swim(n);
}
this.delMax = function(){
var max = pq[1];
exch(1, n--);
pq[n+1] = null;
sink(1);
return max;
}
//由下至上的堆有序化(上浮)的實(shí)現(xiàn)
function swim(k){
while((k > 1) && less(Math.floor(k/2), k)){
exch(Math.floor(k/2), k);
k = Math.floor(k/2);
}
}
//由上至下的堆有序化(下沉)的實(shí)現(xiàn)
function sink(k){
while(2*k <= n){
var j = 2*k;
if((j < n) && less(j, j+1)){
j++;
}
if(!less(k, j)){
break;
}
exch(k, j);
k = j;
}
}
//堆實(shí)現(xiàn)的比較和交換方法
function less(i, j){
return pq[i] < pq[j];
}
function exch(i, j){
var temp = pq[i];
pq[i] = pq[j];
pq[j] = temp;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/90881.html
摘要：隊(duì)列是遵行先進(jìn)先出原則的一組有序的項(xiàng)。優(yōu)先隊(duì)列是默認(rèn)隊(duì)列的變種，它的元素的添加和移除是基于優(yōu)先級的。如此循環(huán)，直至隊(duì)列的長度等于，返回勝者行。同時，還掌握了很著名的優(yōu)先隊(duì)列循環(huán)隊(duì)列這兩種結(jié)構(gòu)。 《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法》讀書筆記。 隊(duì)列是遵行FIFO(First In First Out, 先進(jìn)先出)原則的一組有序的項(xiàng)。隊(duì)列再尾部添加新元素，并從頂部移除元素。 在現(xiàn)實(shí)中...
摘要：隊(duì)列遵循原則的一組有序的項(xiàng)向隊(duì)列尾部添加一個項(xiàng)移除隊(duì)列的第一項(xiàng)返回隊(duì)列中第一項(xiàng)，對隊(duì)列本身不做修改判斷隊(duì)列是否為空返回隊(duì)列包含的元素個數(shù)優(yōu)先隊(duì)列根據(jù)優(yōu)先級添加項(xiàng)最小優(yōu)先隊(duì)列移除隊(duì)列的第一項(xiàng)返回隊(duì)列中第一項(xiàng)，對隊(duì)列本身不做修改判斷隊(duì)列是否 隊(duì)列遵循FIFO（First In First Out）原則的一組有序的項(xiàng) let Queue = (function () { let it...
摘要：棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu)，比如下面介紹的二叉查找樹。 前言 在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務(wù)器端編程。鑒于JavaScript語言已經(jīng)走出了瀏覽器，程序員發(fā)現(xiàn)他們需要更多傳統(tǒng)語言（比如C++和Java）提供的工具。這些工具包括傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)（如鏈表，棧，隊(duì)列，圖等），...
摘要：解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由年在如何從迷宮中尋找出路這一問題中提出。廣度優(yōu)先搜索讓你能夠找出兩樣?xùn)|西之間的最短距離。使用廣度優(yōu)先搜索解決問題。 你經(jīng)常需要解決最短路徑問題(shorterst-path problem)。解決最短路徑問題的算法被稱為廣度優(yōu)先搜索。廣度優(yōu)先搜索算法最早由Edward F. Moore 1959年在如何從迷宮中尋找出路這一...
閱讀 3598·2023-04-26 00:05
閱讀 981·2021-11-11 16:55
閱讀 3576·2021-09-26 09:46
閱讀 3553·2019-08-30 15:56
閱讀 943·2019-08-30 15:55
閱讀 2964·2019-08-30 15:53
閱讀 1976·2019-08-29 17:11
閱讀 841·2019-08-29 16:52
