摘要:堆的算法优先队列是一种抽象数据类型,最重要的操作是删除最大元素和插入元素。用长度为的数组来表示一个大小为的堆,堆元素放在至中,不使用。由下至上的堆有序化上浮的实现由上至下的堆有序化下沉的实现堆实现的比较和交换方法
堆的算法
优先队列是一种抽象数据类型,最重要的操作是删除最大元素和插入元素。
用长度为N+1的数组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; } //由下至上的堆有序化(上浮)的实现 function swim(k){ while((k > 1) && less(Math.floor(k/2), k)){ exch(Math.floor(k/2), k); k = Math.floor(k/2); } } //由上至下的堆有序化(下沉)的实现 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; } } //堆实现的比较和交换方法 function less(i, j){ return pq[i] < pq[j]; } function exch(i, j){ var temp = pq[i]; pq[i] = pq[j]; pq[j] = temp; } }
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/90881.html
摘要:队列是遵行先进先出原则的一组有序的项。优先队列是默认队列的变种,它的元素的添加和移除是基于优先级的。如此循环,直至队列的长度等于,返回胜者行。同时,还掌握了很著名的优先队列循环队列这两种结构。 《学习JavaScript数据结构与算法》读书笔记。 队列是遵行FIFO(First In First Out, 先进先出)原则的一组有序的项。队列再尾部添加新元素,并从顶部移除元素。 在现实中...
摘要:队列遵循原则的一组有序的项向队列尾部添加一个项移除队列的第一项返回队列中第一项,对队列本身不做修改判断队列是否为空返回队列包含的元素个数优先队列根据优先级添加项最小优先队列移除队列的第一项返回队列中第一项,对队列本身不做修改判断队列是否 队列遵循FIFO(First In First Out)原则的一组有序的项 let Queue = (function () { let it...
摘要:栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构,比如下面介绍的二叉查找树。 前言 在过去的几年中,得益于Node.js的兴起,JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器,程序员发现他们需要更多传统语言(比如C++和Java)提供的工具。这些工具包括传统的数据结构(如链表,栈,队列,图等),...
摘要:解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由年在如何从迷宫中寻找出路这一问题中提出。广度优先搜索让你能够找出两样东西之间的最短距离。使用广度优先搜索解决问题。 你经常需要解决最短路径问题(shorterst-path problem)。解决最短路径问题的算法被称为广度优先搜索。广度优先搜索算法最早由Edward F. Moore 1959年在如何从迷宫中寻找出路这一...
阅读 3574·2023-04-26 00:05
阅读 963·2021-11-11 16:55
阅读 3541·2021-09-26 09:46
阅读 3526·2019-08-30 15:56
阅读 919·2019-08-30 15:55
阅读 2946·2019-08-30 15:53
阅读 1959·2019-08-29 17:11
阅读 825·2019-08-29 16:52