`

priority queue

prototype算法XHTMLHTML 
阅读更多
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 
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>


------
分享到：
| chrome 扩展
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    C++ 用linked list写priority queue

    用linked list来写priority queue

    Two-level heaps a new priority queue structure with applications

    Two-level heaps a new priority queue structure with applications to the single source shortest path problem

    优先队列（Priority Queue）是一种特殊类型的队列

    优先队列（Priority Queue）是数据结构中的一种特殊队列，它的主要特点是元素的出队顺序不是按照“先进先出”（FIFO）的原则，而是根据每个元素的优先级来决定。这种数据结构广泛应用于各种算法和系统设计中，如事件...

    Android Priority Job Queue

    Android Priority Job Queue

    priority queue优先级队列

    算法中优先级队列问题...用堆排序的算法来做的例子

    PriorityQueue(eden).cpp

    *push() 将一个元素置于priority queue中 top() 返回priority queue中的“下一个元素” pop() 从priority queue 中移除一个元素 注意：如果priority queue 内没有元素，执行top()和pop()会导致未定义的行为，应该先...

    STL中priority_queue

    STL 中的 priority_queue priority_queue 是 STL 中的一种容器，可以实现优先级队列的功能。下面，我们将详细介绍 priority_queue 的使用方法和实现原理。 priority_queue 的基本概念 priority_queue 是一种特殊...

    优先级队列 priority queue

    优先级队列的实现，包括堆的实现，最大堆的生成

    priority_queue.pdf

    从提供的文件内容来看，文档标题为"priority_queue.pdf"，描述同样为"priority_queue.pdf"，说明该文档是关于优先队列（priority queue）的，它是C++标准模板库（STL）中的一个重要容器。由于文档内容是以OCR扫描...

    20151910042-刘鹏-DSA思考题-08 - Binary Tree and Priority Queue1

    在数据结构与算法的学习中，二叉树和优先级队列是两个重要的概念。以下是关于这两个主题的详细解释和相关知识点： 一、二叉树结构 1. 二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常称为左子节点...

    C++ STL Adaptor stack、queue和vector的使用.doc

    C++ STL Adaptor stack、queue和vector的使用 C++ STL 提供了多种容器类，包括 stack、...以上就是 C++ STL 中 stack、queue 和 priority queue 的使用方法和常见操作。这些容器类可以方便地实现各种数据结构和算法。

    基于python的Priority-Queue.md

    ### 基于 Python 的 Priority-Queue.md #### 1. 优先队列简介 **优先队列（Priority Queue）**是一种特殊类型的队列，在这种队列中，每个元素都被赋予了一个优先级。当需要访问队列中的元素时，具有最高优先级的...

    前端开源库-js-priority-queue

    本文将深入探讨“前端开源库-js-priority-queue”这一主题，它是一个专门为JavaScript设计的优先级队列实现，为前端开发者提供了一种强大的数据结构，用于优化算法和提高代码执行效率。 **优先级队列简介** 优先级...

    C++ 中”priority_queue” 优先级队列实例详解

    C++ 中”priority_queue” 优先级队列实例详解 1. 简介 标准库队列使用了先进先出(FIFO)的存储和检索策略. 进入队列的对象被放置在尾部, 下一个被取出的元素则取自队列的首部. 标准库提供了两种风格的队列: FIFO ...

    Android代码-android-priority-jobqueue

    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.

    priority-queue

    // 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）的功能

    自己编写优类似优先队列数据（priority_queue）的功能，适合上交的课程设计作业

    优先权队列pqueue(Python实现)

    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-priority-queue:具有添加功能的简单Redis工作队列（优先级，一次弹出多个项目）

    Redis优先级队列 redis-priority-queue是一个简单的工作队列，类似于具有以下新增功能： 可以添加具有优先级的项目（介于-9007199254740992和9007199254740992之间） 队列会自动进行重复数据删除（重复的项目在推送...

    Python3 queue队列模块详细介绍

    3. **优先级队列（Priority Queue）**：通过`queue.PriorityQueue(maxsize)`创建，元素按照优先级顺序出队，优先级越高，元素越先被处理。队列中的元素通常需要是可比较的，比如整数或自定义对象，其中定义了`__lt__...

Magicbox
Global site tag (gtag.js) - Google Analytics