博客访问： 152053
博文数量： 112
博客积分： 3092
博客等级： 中校
技术积分： 1172
注册时间：
IT168企业级官微
微信号：IT168qiye
系统架构师大会
微信号：SACC2013
分类： C/C++
以操作系统对任务队列的处理原理提出来优先队列这个概念，在操作系统对任务的调度中，任务队列并不是简单的FIFO形式，而是以一定的优先级被调用的，这个队列就是优先队列，调度上带有级别区分的队列。
优先队列中至少要存在两种操作：insert和deletemin，前者对应着元素入队，后者对应于出队。
可以以很多方式实现优先队列，比如链表，这样插入操作只需要O(1)的时间，但是删除最小元的时间为O(N),也可以用二叉查找树，这样两种操作的平均运行时间都为O(logN).
对于优先队列最普遍的实现是：二叉堆。
堆是一棵从左到右填满的二叉树，当然底层例外，堆可以由简单的数组来表征，对于数组位置i上的元素，它的左孩子在2i上，右孩子在2i+1上，父亲则在[i/2]上，对于堆，为了便于上述两种操作的执行，定义一种堆序性质，即：在一个堆中，对于每一个节点X，X父亲的关键字小于等于X的关键字，根结点除外。
这样我们可以给出一些基本的堆操作的算法：
思路是基于一种“上滤”的策略，设堆为H,待插入的元素为X,首先在size+1的位置建立一个空穴，然后比较X和空穴的爸爸的大小，把“大的爸爸”换下来，以此推进，最后把X放到合适的位置。
2.DELETEMIN
与上面的上滤对应，这将是一种“下滤”的策略，就是逐层推进，把较小的孩子换上来，这里面有个小的问题在具体算法实现上要注意，设堆的最后一个元素是L,在推进到倒数第二层时，将导致最后一层的某个孩子被换上去而产生一个洞，这时候为了保持堆的结构，必须把最后一个元素运过去补上，此时就存在一个问题，如果L比那个孩子小的话就不能保证堆序的性质了，所以在程序中要加一个if语句来进行这个边界条件的处理，还是那句话，对于一个完整的程序，算法是重要的一方面，而对算法边界问题的处理则是更重要的一方面。
堆还有其他一些操作，不详细笔记了。
最后在说一个堆的应用：
场景：求N个元素的第k个小的元素
算法1：将N个元素排序，取出第k个& O(N)
算法2：取出N个元素的前k个进行排序，然后依次取出N-k个元素，每一个元素都和第k个元素比较，如果比它小，那就把第k个元素删除，然后将该元素插入到适当的位置，重新组成k个元素 O(NK)
算法3：使用堆，使用这N个元素构造堆（O(N)），然后进行k次deletemin（O(klogN)），总的运行时间
O(N+klogN)。当k较大时这个时间为O(klogN)，对于小的k值为O(N).
阅读(1458) | 评论(2) | 转发(0) |
相关热门文章
给主人留下些什么吧！~~
加上中文文法,应该是
这样删除最小元的时间只为O(1)，但是插入操作需要O(n)的时间
这样插入操作只需要O(1)的时间，但是删除最小元的时间为O(N)
时间复杂度的评判掉过来了.应该是这样插入操作只需要O(n)的时间，但是删除最小元的时间为O(1)
请登录后评论。数据结构-优先队列（堆实现） - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 15时,
的添加、 删除& Java实现
代码片段(2)
JPriorityQueue.java&~&3KB&&&&
package com.structures.
import java.util.NoSuchElementE
public class JPriorityQueue&E& {
QueueNode&E&
public JPriorityQueue(int capacity) {
node = new QueueNode&E&(capacity);
node.size = 0;
node.queue = (E[]) new Object[capacity + 1];
public void add(E x) {
int k = node.
while (k & 0) {
int parent = (k - 1) / 2;
E data = node.queue[parent];
Comparable&E& key = (Comparable)
if (pareTo(data) &= 0)
node.queue[k] =
node.queue[k] =
node.size++;
public E remove() {
int parent = 0;
if (node.size == 0) {
throw new NoSuchElementException("queue is null");
E min = node.queue[0];// top
E last = node.queue[node.size - 1];// last
node.queue[0] =// add the last to top
node.queue[node.size - 1] =
node.size--;
Comparable&? super E& complast = (Comparable&? super E&)
if (node.size == 2 && pareTo(node.queue[1]) & 0) { // 只剩下最后两个结点，进行比较
node.queue[0] = node.queue[1];
node.queue[1] =
if (node.size & 2) { // 大于三个结点的，向下旋转
while (parent & node.size / 2) {
int left = 2 * parent + 1;// left child
int right = left + 1;// right child
E root = node.queue[parent];
Comparable&? super E& comproot = (Comparable&? super E&)
if (pareTo(node.queue[left]) & 0
&& pareTo(node.queue[right]) & 0)
Comparable&? super E& compleft = (Comparable&? super E&) node.queue[left];
if (pareTo(node.queue[right]) &= 0) {
node.queue[parent] = node.queue[left];
node.queue[left] =
node.queue[parent] = node.queue[right];
node.queue[right] =
if (right * 2 &= node.size)
public static void main(String[] args) {
JPriorityQueue&String& queue = new JPriorityQueue&String&(10);
queue.add("Z");
queue.add("B");
queue.add("QZA");
queue.add("QBA");
queue.add("EAA");
queue.add("A");
// queue.remove();
// queue.remove();
// queue.remove();
// queue.remove();
// queue.remove();
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
System.out.println(queue.remove());
QueueNode.java&~&163B&&&&
package com.structures.
public class QueueNode&E& {
QueueNode(int capacity){
this.capacity=
开源中国-程序员在线工具：
开源从代码分享开始
扁-哥的其它代码结构之美——优先队列基本结构（四）——二叉堆、d堆、左式堆、斜堆 - 学步园
结构之美——优先队列基本结构（四）——二叉堆、d堆、左式堆、斜堆[0评]
实现优先队列结构主要是通过堆完成，主要有：二叉堆、d堆、左式堆、斜堆、、、等。
完全二叉树，根最小。
存储时使用层序。
(1). insert（上滤）
插入末尾 26，不断向上比较，大于26则交换位置，小于则停止。
(2). deleteMin（下滤）
提取末尾元素，放在堆顶，不断下滤：
(3). 其他操作：
都是基于insert（上滤）与deleteMin（下滤）的操作。
减小元素：减小节点的值，上滤调整堆。
增大元素：增加节点的值，下滤调整堆。
删除非顶点节点：直接删除会出问题。方法：减小元素的值到无穷小，上滤后删除。
Merge：insert one by one
完全d叉树，根最小。
存储时使用层序。
2.2. 操作:
操作跟二叉堆基本一致：insert,deleteMin,增大元素，减小元素，删除非顶元素，merge。
2.3 二叉堆与d叉堆的对比：
零路径长度：到没有两个儿子的节点最短距离
1.一棵二叉树
2.零路径长：左儿子≧右儿子，父节点= min{儿子}
+1（这条性质导致了左式堆的严重左偏）
零路径长度：
3.2. 操作:
(1) merge :
原则:根值大的堆与根值小的堆的右子堆合并(根值：根位置的元素值，并非零路径长度)
具体分三种情况（设堆H1的根值小于H2）
H1只有一个节点
H1根无右孩子
H1根有右孩子
(1.1).H1只有一个节点，若出现不满足：零路径长：左儿子≧右儿子，交换左右孩子。
(1.2).H1根无右孩子，若出现不满足：零路径长：左儿子≧右儿子，交换左右孩子。
(1.3).H1根有右孩子
1.初始状态，H1的根6，H2的根为8，将H2合并到H1。
2.将H1构造成根无右孩子的形式：
3.将元素10, merge到H2，要首先将H2构造成根无右孩子的形式，递归，merge，若出现不满足：零路径长：左儿子≧右儿子，交换左右孩子……
——》——》——》
3.3. 性质分析:
insert：merge
deleteMin：delete root，merge
时间复杂度：merge与右路径长度之和成正比；最坏O(logN)
缺点：交换需判断；维护零路径长
二叉树，根最小。由此可见：
特点：merge无条件交换。
时间复杂度：最坏O(N)；最好Ohm(1)；平均O(logN)
4.2性能比较：
如果是不支持所谓的合并操作union的话，普通的堆数据结构就是一种很理想的数据结构（堆排序）。 但是如果想要支持集合上的合并操作的话，最好是使用二项堆或者是斐波那契堆，普通的堆在union操作上最差的情况是O(n)，但是二项堆和斐波那契堆是O(lgn)。
Binary heap
Binomial heap
Fibonacci heap
二叉堆（最坏情况） 二项堆（最坏情况）（斐波那契堆（平摊））
(worst-case)
(worst-case)
(amortized)
--------------------------------------------------------------
EXTRACT-MIN
DECREASE-KEY
完整的PPT下载：
+++相关文章+++
没有相关文章!堆、优先级队列和堆排序 - 开源中国社区
当前访客身份：游客 [
当前位置：
堆结构是一种数组对象，其定义如下：它是完全二叉树或者近似完全二叉树。经常作为优先级队列，比如二叉树优先级队列，四叉树优先级队列。
n个关键字序列Kl，K2，…，Kn称为（Heap），当且仅当该序列满足如下性质（简称为堆性质）：
(1)ki&=k(2i）且ki&=k(2i+1)(1≤i≤ n），当然，这是小根堆，大根堆则换成&=号。
&&&&&&& k(i）相当于二叉树的非叶结点，K(2i）则是左孩子，k(2i+1）是右孩子
若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：
树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若存在）结点的关键字。
优先级队列是不同于先进先出队列的另一种队列。
最大优先级队列，是这样的一种队列结构，它的内部存放着一系列的元素，每个元素都对应着一个最优级，
最大优先级队列不管各元素的入队顺序，在出队时，总是对应优先级最大的元素出队。
最小优先级队列正好相反，不管入队的顺序，对应的权值最小的队列元素出队列。
优先级队列可以用二叉树来实现，比如最大元素出队列，只要在二叉树中用常数时间取出最大值就可以了。取出了最大值之后，要继续调整树的状态，使得第二大节点放入根节点。
基本思想：对一组待排序记录的关键字，首先建立一个堆，然后输出最大（小）关键字，使得其余的关键字重新构成一个堆，得到次大（小）的元素。这样反复执行，使得记录成为一个有序序列，这个过程就称为堆排序。由此可见，堆排序主要解决两个问题：（1）如何使得一个无序的序列称为一个有序的序列；（2）如何在输出对顶元素之后，调整剩余元素使之称为一个堆。
调整堆的过程：从非终端节点开始，一直到最后节点。
//调整堆使之称为大（小）顶堆
void HeapAdjust(int *data,int s,int m)
int rc = data[s];
for (j = 2 * j & j *= 2) //沿着关键字较大的孩子节点向下筛选
if (j & m && data[j] & data[j+1])
++j; //j是值较大元素的下标
if (!(rc&data[j]))
data[s] = data[j];
//rc应插入在位置s上
而建立堆只要从最后一个非叶子节点开始，向前逐步调整，这种调整的方法常称为“筛选法”。
void Heap_Sort(int* a,int n)
int i = 0;
for (i=n/2; i&0; i--) //把a建成大顶堆
HeapAdjust(a,i,n-1);
//临时变量
for (i=n-1; i&0; i--)
//将当前节点和最后一个数据交换
temp = a[0];
a[0] = a[i];
HeapAdjust(a,0,i-1);
堆排序的优点：平均时间复杂度是最坏时间复杂度都是O（nlogn），效率比较高。仅仅需要一个供交换用的辅助记录大小空间。
缺点：不稳定，相同的数据元素在排序过程中可能移动位置。对于记录数较少的排序不适合。
原文链接：
共有0个评论
更多开发者职位上
有什么技术问题吗？
长平狐的其它问题这里面说堆实际上是一种优先队列的结构，第一元素有最高优先权，这是什么意思？栈的后进先出又是什么意思_百度知道