- 浏览: 442696 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
priority queue
priority queue , 基于 heap,封装了一些操作而实现 优先级队列 的功能,
------
分类:
* max-queue:
对应 max-heap,
用于取出最大的值,
应用:
任务队列 (高优先级先执行)
* min-queue
对应 min-heap,
用于取出最小的值,
应用:
事件触发队列 (触发时间小的先执行)
------
priority queue 的 operation
max-queue:
* INSERT(S, x)
将 x 放入 set S 中,
可记为: S ← S ∪ {x}
* MAXIMUM(S)
返回 set S 中 有最大 key 的 元素
* EXTRACT-MAX(S)
删除 并 返回 set S 中 有最大 key 的 元素
* INCREASE-KEY(S, x, k)
增大 元素 x 的 key 到 k,(k >= x'key),
相当于提高优先级
*
min-queue:
* INSERT(S, x)
将 x 放入 set S 中,
可记为: S ← S ∪ {x}
* MINIMUM(S)
返回 set S 中 有最小 key 的 元素
* EXTRACT-MIN(S)
删除 并 返回 set S 中 有最小 key 的 元素
* DECREASE-KEY(S, x, k)
减小 元素 x 的 key 到 k,(k <= x'key),
相当于提前
*
------
max-queue 的 实现
* HEAP-MAXIMUM(A)
直接取 heap 顶部的元素 即可,
即 return A[1],
时间复杂度:O(1)
* HEAP-EXTRACT-MAX(A)
首先取 heap 顶部元素,然后再 执行一次 max-heap 操作,将剩余的最大值放到 heap 顶部,
时间复杂度:O(lg n)
* HEAP-INCREASE-KEY(A, i, key)
将 key 增大,然后向上和 parent note 节点比较,直到找到比自己大的 parent note,
时间复杂度:O(lg n)
* MAX-HEAP-INSERT(A, key)
首先将新 元素的 key 设为 -∞,放在 heap 的最后,
然后用调用 1次 HEAP-INCREASE-KEY(A, i, key),即可 将 key 设置到希望的值,
时间复杂度:O(lg n)
*
总结:
max-queue 的任意操作,都可以用一组 O(lg n) 操作实现,
------
min-queue 的实现
类似 max-queue
------
例子:
* js
* html
------
priority queue , 基于 heap,封装了一些操作而实现 优先级队列 的功能,
------
分类:
* max-queue:
对应 max-heap,
用于取出最大的值,
应用:
任务队列 (高优先级先执行)
* min-queue
对应 min-heap,
用于取出最小的值,
应用:
事件触发队列 (触发时间小的先执行)
------
priority queue 的 operation
max-queue:
* INSERT(S, x)
将 x 放入 set S 中,
可记为: S ← S ∪ {x}
* MAXIMUM(S)
返回 set S 中 有最大 key 的 元素
* EXTRACT-MAX(S)
删除 并 返回 set S 中 有最大 key 的 元素
* INCREASE-KEY(S, x, k)
增大 元素 x 的 key 到 k,(k >= x'key),
相当于提高优先级
*
min-queue:
* INSERT(S, x)
将 x 放入 set S 中,
可记为: S ← S ∪ {x}
* MINIMUM(S)
返回 set S 中 有最小 key 的 元素
* EXTRACT-MIN(S)
删除 并 返回 set S 中 有最小 key 的 元素
* DECREASE-KEY(S, x, k)
减小 元素 x 的 key 到 k,(k <= x'key),
相当于提前
*
------
max-queue 的 实现
* HEAP-MAXIMUM(A)
直接取 heap 顶部的元素 即可,
即 return A[1],
时间复杂度:O(1)
* HEAP-EXTRACT-MAX(A)
首先取 heap 顶部元素,然后再 执行一次 max-heap 操作,将剩余的最大值放到 heap 顶部,
时间复杂度:O(lg n)
* HEAP-INCREASE-KEY(A, i, key)
将 key 增大,然后向上和 parent note 节点比较,直到找到比自己大的 parent note,
时间复杂度:O(lg n)
* MAX-HEAP-INSERT(A, key)
首先将新 元素的 key 设为 -∞,放在 heap 的最后,
然后用调用 1次 HEAP-INCREASE-KEY(A, i, key),即可 将 key 设置到希望的值,
时间复杂度:O(lg n)
*
总结:
max-queue 的任意操作,都可以用一组 O(lg n) 操作实现,
------
min-queue 的实现
类似 max-queue
------
例子:
* js
var arr_max_priority_queue = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ]; // 依赖于前面的 heap_sort.js 中,HeapSort 类 /** * max-priority-queue * 用于取出最大的值,如 任务队列 * 算法复杂度:max-queue 的任意基本操作(除初始 建立 max-heap 外),都可以用一组 O(lg n) 操作实现, * * @param keyArr * @return */ function MaxPriorityQueue(arr) { this.arr = arr; this.heapsort = new HeapSort(arr); } /** * 执行1次 max-heap 操作 * * @param arr * @return */ MaxPriorityQueue.prototype.buildMaxHeap = function() { this.heapsort.buildMaxHeap(this.arr); }; /** * 执行排序 * @return */ MaxPriorityQueue.prototype.sort = function() { this.arr = this.heapsort.sort().reverse(); }; /** * 获得 最大优先级的值,即 heap 顶部的元素 * * @return */ MaxPriorityQueue.prototype.maximum = function() { return arr.length > 0 ? arr[0] : undefined; }; /** * 获得 最大优先级的值,并将该值从 queue 中删除,即 heap 顶部的元素 * * @return */ MaxPriorityQueue.prototype.extractMax = function() { if (arr.length > 0) { // no element return undefined; } var max = this.arr.shift(); this.buildMaxHeap(); return max; }; /** * 值增大后,将元素在 heap 中 上移 * * @param index * @param value * @return */ MaxPriorityQueue.prototype.increase = function(index, value) { this.arr[index] = value; var curIndex = index; var parentIndex; while (curIndex != 0) { parentIndex = this.heapsort.parent(curIndex + 1) - 1; if (this.arr[curIndex] > this.arr[parentIndex]) { var tmp = this.arr[curIndex]; this.arr[curIndex] = this.arr[parentIndex]; this.arr[parentIndex] = tmp; curIndex = parentIndex; } else { // ok,break while break; } } }; /** * 插入1个值,先放在最后,然后调用 increase() 将其放到适当位置 * * @param element * @return */ MaxPriorityQueue.prototype.insert = function(element) { this.arr.push(element); this.increase(this.arr.length - 1, element); };
* html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <script type="text/javascript" src="js/heap_sort.js"></script> <script type="text/javascript" src="js/max_priority_queue.js"></script> </head> <body> <input type="button" value="heap sort" onclick="alert(new HeapSort(arr_heap).sort());" /> <input type="button" value="max priority queue" onclick="var mpq = new MaxPriorityQueue(arr_max_priority_queue);mpq.sort();mpq.insert(190);alert(mpq.arr);" /> </body> </html>
------
发表评论
-
c - linkedlist
2012-05-10 14:52 1079c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1722c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1203random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1076sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1070max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1088binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1004bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1592linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4047queue ------ 结构 线性存 ... -
Medians and Order Statistics (次序统计)
2011-01-03 14:36 2825Medians and Order Statistics - ... -
counting sort
2011-01-02 20:36 1561counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1187quicksort ------ quicksort ove ... -
heap sort
2010-12-18 19:09 1202heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1147merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1042insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2187以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2626排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
已排序数组 a,求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1597已排序数组 a,求其元素的绝对值 共有多少个不同的值? ... -
binary search
2010-08-29 19:35 966binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1184算法导论(2nd) 结构 * <Introductio ...
相关推荐
用linked list来写priority queue
Two-level heaps a new priority queue structure with applications to the single source shortest path problem
优先队列(Priority Queue)是数据结构中的一种特殊队列,它的主要特点是元素的出队顺序不是按照“先进先出”(FIFO)的原则,而是根据每个元素的优先级来决定。这种数据结构广泛应用于各种算法和系统设计中,如事件...
Android Priority Job Queue
算法中优先级队列问题...用堆排序的算法来做的例子
*push() 将一个元素置于priority queue中 top() 返回priority queue中的“下一个元素” pop() 从priority queue 中移除一个元素 注意:如果priority queue 内没有元素,执行top()和pop()会导致未定义的行为,应该先...
STL 中的 priority_queue priority_queue 是 STL 中的一种容器,可以实现优先级队列的功能。下面,我们将详细介绍 priority_queue 的使用方法和实现原理。 priority_queue 的基本概念 priority_queue 是一种特殊...
优先级队列的实现,包括堆的实现,最大堆的生成
从提供的文件内容来看,文档标题为"priority_queue.pdf",描述同样为"priority_queue.pdf",说明该文档是关于优先队列(priority queue)的,它是C++标准模板库(STL)中的一个重要容器。由于文档内容是以OCR扫描...
在数据结构与算法的学习中,二叉树和优先级队列是两个重要的概念。以下是关于这两个主题的详细解释和相关知识点: 一、二叉树结构 1. 二叉树是一种特殊的树形数据结构,每个节点最多有两个子节点,通常称为左子节点...
C++ STL Adaptor stack、queue和vector的使用 C++ STL 提供了多种容器类,包括 stack、...以上就是 C++ STL 中 stack、queue 和 priority queue 的使用方法和常见操作。这些容器类可以方便地实现各种数据结构和算法。
### 基于 Python 的 Priority-Queue.md #### 1. 优先队列简介 **优先队列(Priority Queue)**是一种特殊类型的队列,在这种队列中,每个元素都被赋予了一个优先级。当需要访问队列中的元素时,具有最高优先级的...
本文将深入探讨“前端开源库-js-priority-queue”这一主题,它是一个专门为JavaScript设计的优先级队列实现,为前端开发者提供了一种强大的数据结构,用于优化算法和提高代码执行效率。 **优先级队列简介** 优先级...
C++ 中”priority_queue” 优先级队列实例详解 1. 简介 标准库队列使用了先进先出(FIFO)的存储和检索策略. 进入队列的对象被放置在尾部, 下一个被取出的元素则取自队列的首部. 标准库提供了两种风格的队列: FIFO ...
Priority Job Queue is an implementation of a Job Queue specifically written for Android to easily schedule jobs (tasks) that run in the background, improving UX and application stability.
// Creating a new priority queue. var queue = new PriorityQueue(function (a, b) { return a - b; }); // Adding elements to the queue. queue.enqueue(2); queue.enqueue(0); queue.enqueue(1); // Removing...
自己编写优类似优先队列数据(priority_queue)的功能,适合上交的课程设计作业
Use a binary Max-Heap to implement a Priority Queue. Your priority queue class will be a wrapper for the functions in your heap class. Your heap should be implemented using a list, L. Recall, if a ...
Redis优先级队列 redis-priority-queue是一个简单的工作队列,类似于具有以下新增功能: 可以添加具有优先级的项目(介于-9007199254740992和9007199254740992之间) 队列会自动进行重复数据删除(重复的项目在推送...
3. **优先级队列(Priority Queue)**:通过`queue.PriorityQueue(maxsize)`创建,元素按照优先级顺序出队,优先级越高,元素越先被处理。队列中的元素通常需要是可比较的,比如整数或自定义对象,其中定义了`__lt__...