优先级队列是一个抽象数据类型,它提供删除插入、最大(最小)关键字值数据项的方法,其主要目的是对极值提供便利的访问。
优先级队列可以用有序数组来实现,也可以用队列来实现。
堆,是一种树,由其实现优先级队列的插入删除操作的时间复杂度都是O(logN)。
堆是有如下特点的二叉树:
1.是完全二叉树。即,除了树的最后一层节点不是满的,其他的每一层都必须是满的。
2.堆中的每一个节点都满足堆的条件,即每一个节点的关键字的值都大于或等于其子节点的关键字的值,而小于父节点关键字的值。
3.最大数据项总是在根位置上。
4.一般用数组实现。
5.堆不能有序地遍历所有数据,不能找到特定关键字数据项的位置,也不能移除特定关键字的数据项。
6.要插入的数据项总是先放在数组中的第一个空的位置上,然后再向上筛选它至适当的位置。
7.当从根移除一个数据项时,用数组中的最后一个数据项代替他的位置,然后再向下筛选这个节点到适当的位置。
8.可以更改任意数据项的优先级。首先,更改其关键字,如果增加,则向上筛选,减少,则向下筛选。
堆排序,是一种高效的排序过程,其时间复杂度为O(N*logN).将一个待排序数组依次写入到堆中,写入完毕之后,依次去除根元素(最大元素)写入到数组中,即完成了排序。可以使用同一个数组来存放初始无序的数据、正在排序的数据以及排好序的数据,因此,堆排序不需要额外的空间。(N次插入,N次移除)。
也可以对无序数组的N/2个数据项进行trickDown()操作,而不作N次插入,可使堆排序运行速度更快。
下面是用数组实现的堆以及堆排序:
package test;
public class Heap {
Node2[] heapArray;
int arraySize;// 数组大小
int currentSize;// 数组中实有数据的大小
public Heap(int size) {
arraySize = size;
currentSize = 0;
heapArray = new Node2[arraySize];
}
public boolean isEmpty() {
return currentSize == 0;
}
// 插入
public boolean insert(int key) {
if (currentSize == arraySize)
return false;
Node2 node = new Node2(key);// 创建新节点
heapArray[currentSize] = node;// 将新节点放在数组末尾
trickUp(currentSize++);// 将其向上筛选,同时计数加1
return true;
}
/**
* 节点初始时插入到数组中的空的位置,即最后的位置, 但是如果新插入的节点大于它得到的父节点时,会把堆破坏,
* 因此,需要向上筛选新节点,直到它在一个大于它的父节点之下,在一个小于它的子节点之上。
*/
public void trickUp(int index) {
int parent = (index - 1) / 2;// 父节点的下标
Node2 bottom = heapArray[index];
while (index > 0 && heapArray[parent].idata < bottom.idata) {
heapArray[index] = heapArray[parent];// 向下移动父节点
index = parent;// 将index上移
parent = (parent - 1) / 2;// 父节点的下标给予其父节点
}
heapArray[index] = bottom;
}
// 删除根节点
public Node2 remove() {
Node2 root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickDown(0);// 向下筛选
return root;
}
/**
* 将根节点删除之后,需要找到一个适合的节点来替换之
*/
public void trickDown(int index) {
int largerChild;
Node2 top = heapArray[index];
while (index < currentSize / 2) {
int leftChild = index * 2 + 1;
int rightChild = leftChild + 1;
if (rightChild < currentSize
&& heapArray[leftChild].idata < heapArray[rightChild].idata)
largerChild = rightChild;
else
largerChild = leftChild;
if (top.idata >= heapArray[largerChild].idata)
break;
heapArray[index] = heapArray[largerChild];
index = largerChild;
}
heapArray[index] = top;
}
public void show() {
for (int i = 0; i < currentSize; i++) {
if (heapArray[i] != null)
System.out.println(heapArray[i].idata + " ");
else
System.out.println("* ");
}
}
public static void main(String[] args) {
Heap heap = new Heap(6);
heap.insert(12);
heap.insert(23);
heap.insert(4);
heap.insert(2);
heap.insert(8);
heap.show();
Node2 node = heap.remove();
System.out.println("the remove node = " + node.idata);
heap.show();
// 堆排序
Item[] item = { new Item(3), new Item(1), new Item(5), new Item(2),
new Item(7) };
for (int i = 0; i < item.length; i++)
heap.insert(item[i].idata);
for (int i = 0; i < item.length; i++) {
n = heap.remove();
item[i].idata = n.idata;
}
//打印数组
for (int i = 0; i < item.length; i++)
System.out.print(item[i].idata + " . ");
}
}
class Node2 {
int idata;
public Node2(int idata) {
this.idata = idata;
}
}
分享到:
相关推荐
数据结构课设——小大根交替堆实现的双端优先级队列及应用 小大根交替堆是一种特殊的堆结构,它可以同时满足大根堆和小根堆的性质。在本文中,我们将对小大根交替堆实现的双端优先级队列进行详细的分析和设计。 ...
使用c++模板实现的堆排序、优先级队列,在vs2010下编译运行通过。压缩文件里为两个工程文件,如果有vs2010的话解压缩打开sln文件就可以了,没有的话,新建工程将文件复制过去就ok了。如果有问题可以留言。
数据结构与算法Python语言描述DS优先级队列和堆排序PPT学习教案.pptx
数据结构与算法(Python语言描述)DS053优先级队列和堆排序ppt课件.ppt
优先队列是一种数据结构,它类似于常规的队列或栈,但每个元素都有与之关联的“优先级”。在优先队列中,元素的出队顺序是基于它们的优先级,而不是它们进入队列的顺序。具有最高优先级的元素将首先出队,而具有最低...
通过使用具有二项式堆结构的优先级队列来观察简单的搜索引擎来应用数据结构。 解释 在WWW中,当您输入“关键字”时,搜索引擎会尝试根据关键字与上的文档之间的相似性来对文档进行排名。 最著名的搜索引擎是Google...
算法和数据结构项目:优先级队列 以排序向量,未排序向量和堆的形式实现优先级队列。 实现之间的比较,显示了Heap数据结构的优点。
课程的目录结构如下,每一章都有配套的文字讲义(markdown),示例代码,视频讲解,详细的讲解一般会放在视频...python 内置常用数据结构和算法的使用。list, dict, set, collections 模块,heapq 模块 面试笔试常考算法
数据结构各种算法实现(C++模板) 数据结构各种算法实现(C++模板)暑假在家不能上网,把数据结构的一些算法实现了...9、优先级队列 10、串 11、二叉树 12、线索二叉树 13、堆 14、哈夫曼树 15、树 16、B+树 17、图 18、排序
Heap.js JavaScript / TypeScript的高效二进制堆(优先级队列,二进制树)数据结构。 包括JavaScript方法,Python的heapq模块方法和Java的PriorityQueue方法。 易于使用,已知接口,经过测试并有据可查JavaScript二...
优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 小结...
优先队列优先队列是一种基于堆实现的数据结构,它允许元素按照优先级顺序进行访问。在计算机科学中,优先队列是一种重要的数据结构,用于实现优先级调度、网络流控、事件处理、多线程同步和数据挖掘等功能。 优先...
全书共分为15章,分别讲述了基本概念、数组、简单排序、堆和队列、链表、递归、进阶排序、二叉树、红黑树、哈希表及图形等知识。附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程...
堆 Go中堆数据结构的参考实现 ... :Fibonacci堆是用于优先级队列操作的数据结构,由一组按堆排序的树组成。 它具有比包括二进制堆和二项式堆在内的许多其他优先级队列数据结构更好的摊销运行时间。 :二项式
优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 ...
优先级队列 解析算术表达式 小结 问题 实验 编程作业 第5章 链表 链结点(Link) LinkList专题Applet 单链表 查找和删除指定链结点 双端链表 链表的效率 抽象数据类型 有序链表 双向链表 迭代器 小结 问题 实验 编程...