`

priority queue

阅读更多
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>


------
分享到:
评论

相关推荐

    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__...

Global site tag (gtag.js) - Google Analytics