这几天查阅了一些关于优先队列的资料，记得我们用优先队列的时候也是在做那个哈弗曼编码的时候，计算每个字符出现的频率之后，再将出现次数越多的就放在靠近树根越近的位置，就在这里用到了优先队列，刚开始真的不懂优先队列是干嘛的，不晓得为什么要存在这么一个东西，搞得自己好茫然的，后来看了源代码什么的之后，才发现它是这么简单！
在这之前我们都了解了一些有关于队列的知识，优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。优先队列也是要涉及到查找和排序的一类数据结构：
A、查找的方法有以下几种：
1、静态查找
2、动态查找
B、排序的方法有以下几种：
1、直接插入排序法
2、折半插入排序法
3、起泡排序法
4、快速排序法
5、简单选择排序法
6、基数排序法
7、堆排序法
8、归并排序法
这里再温习一下数据结构的知识吧！
数据结构的四种基本结构为：
集合 2、线性结构 3、树形结构 4、网状结构
数据的逻辑结构（有时就叫做数据结构）：
线性结构（线性表等）、非线性结构（树、图等）
数据的物理结构（存储结构）：
顺序存储结构、链式存储结构、索引存储结构、散列存储结构
完全二叉树的性质：
如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系：
1、若i = 0, 则 i 无双亲.
2、若i > 0, 则 i 的双亲为：(i -1)/2.?
3、若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2.
4、若结点编号i为偶数，且i!=0,则左兄弟结点i-1.
5、若结点编号i为奇数，且i!=n-1,则右兄弟结点为i+1.
6、结点i 所在层次为：log2(i+1)+1
这里优先队列是用的堆排序法，算法主要运用在于插入和删除：
代码：
/**
* 添加数据
* @param e:要添加的数据对象
* @return:是否添加成功
*/
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
//不能放入空数据
if (e == null)
throw new NullPointerException();
//队列中的数据的个数
currentCount++;
//在装数据之前队列中数据的个数
int i = size;
//当容量不足的时候
if (i >= queue.length)
grow(i + 1);
size = i + 1;
//当队列中还没有元素的时候
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
/**
* 将数据X添加进队列:要进行对比
* @param k:队列的在加入这个数据之前的长度
* @param x:数据对象
*/
private void siftUp(int k, E x) {
//有比较对象的队列的处理方法
if (comparator != null)
siftUpUsingComparator(k, x);
else
//没有比较对象的队列的处理方法
siftUpComparable(k, x);
}
//运用堆排序将数据插入到队列中
private void siftUpComparable(int k, E x) {
//则数据就应该实现Comparable接口
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = (E)e;
k = parent;
}
queue[k] = key;
}
//运用堆排序将数据插入到队列中
private void siftUpUsingComparator(int k, E x) {
while (k > 0) {
int parent = (k - 1) >>> 1;
Object e = queue[parent];
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = (E)e;
k = parent;
}
queue[k] = x;
}
/**
* 移除数据O
* @param o
* @return
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
/**
* 移除指定位置的数据
* @param i
* @return
*/
private E removeAt(int i) {
//断言设定
assert i >= 0 && i < size;
currentCount++;
int s = --size;
//移除最后一个元素
if (s == i)
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
/**
* 移除第K个位置的数据，将数据X加入到队尾
* @param k:要移除的数据在队列中的位置
* @param x:队列中最后一个数据
*/
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
//同样用最小堆将这个数据删除掉
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = (E)c;
k = child;
}
queue[k] = (E)key;
}
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0)
break;
queue[k] = (E)c;
k = child;
}
queue[k] = x;
}
这里用另外一种排序方式：折半插入排序
代码
/**
* 添加数据
* @param e:要添加的数据对象
* @return:是否添加成功
*/
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
//不能放入空数据
if (e == null)
throw new NullPointerException();
currentCount++;
int i = size;
//当容量不足的时候
if (i >= queue.length){
queue = Arrays.copyOf(queue, queue.length+1);
}
size = i + 1;
//当队列中还没有元素的时候
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
/**
* 将数据X添加进队列:要进行对比
* @param k:队列的在加入这个数据之前的长度
* @param x:数据对象
*/
private void siftUp(int k, E x) {
//有比较对象的队列的处理方法
if (comparator != null)
siftUpUsingComparator(k, x);
else
//没有比较对象的队列的处理方法
siftUpComparable(k, x);
}
//运用堆排序将数据插入到队列中
private void siftUpComparable(int k, E x) {
//则数据就应该实现Comparable接口
Comparable<? super E> key = (Comparable<? super E>) x;
//得到中间位置的数据
int parent = (k - 1) >>> 1;
//用两个变量来记录数组前后对比是所需要的位置标记
int low=0,high=k-1;
while ((high-low)>1) {
Object e = queue[parent];
if (key.compareTo((E) e) >= 0){
//再跟后面的比较
low = parent;
parent = (low+high)>>>1;
}else{
//跟前面的比较
high = parent;
parent = (low+high)>>>1;
}
}
//将该数据与low=high位置的数据比较
Object e = queue[low];
if(key.compareTo((E) e) >= 0){
//将数据放在low的后面
for(int i=k;i>low+1;i--){
queue[i-1]=queue[i-2];
}
}else{
//在low位置之前将e放进数组
for(int i=k;i>low-1;i--){
queue[i-1]=queue[i-2];
}
}
}
//运用堆排序将数据插入到队列中
private void siftUpUsingComparator(int k, E x) {
//得到中间位置的数据
int parent = (k - 1) >>> 1;
//用两个变量来记录数组前后对比是所需要的位置标记
int low=0,high=k-1;
while (parent > 0) {
Object e = queue[parent];
if((high-low)<=1){
break;
}
if (comparator.compare(x, (E)e)>=0){
//再跟后面的比较
low = parent;
high = k-1;
parent = parent+(k-parent)>>>1;
}else{
//跟前面的比较
low = 0;
high = parent;
parent = (k-parent)>>>1;
}
}
//将该数据与low=high位置的数据比较
Object e = queue[low];
if(comparator.compare(x, (E)e)>=0){
//将数据放在low的后面
for(int i=k;i>low;i--){
queue[i-1]=queue[i-2];
}
}else{
//在low位置之前将e放进数组
for(int i=k;i>low-1;i--){
queue[i-1]=queue[i-2];
}
}
}
/**
* 移除数据O
* @param o
* @return
*/
public boolean remove(Object o) {
int i = indexOf(o);
if (i == -1)
return false;
else {
removeAt(i);
return true;
}
}
/**
* 移除指定位置的数据
* @param i
* @return
*/
private E removeAt(int i) {
//断言设定
assert i >= 0 && i < size;
currentCount++;
int s = --size;
//移除最后一个元素
if (s == i)
queue[i] = null;
else {
for(int j=i;j<s-1;j++){
queue[j]=queue[j+1];
}
}
return null;
}
之后我用系统的优先队列、我用堆排序的优先队列、折半插入排序的优先队列分别进行测试，结果如下：
用堆排序的都是用的100万数据进行测试的！
系统的测试结果：
插入的时间为-->248
我的测试结果：
插入的时间为-->252
折半插入排序法测试结果为：
插入的时间为-->31912（还只是10万数据啊！！！！）
不晓得这是偶然还是怎么的，就觉得这个结果怪怪的，因为按理论上来说，折半排序不可能这么慢的啊。。。但我测出来就是有问题呃。。。
最后附上一点点小知识：
Comparable与Comparator的区别与联系
左移与右移运算：可以用于寻找节点的根节点和左右孩子节点
>>右移运算：相当于除以2^n
<<左移运算：相当于乘以2^n
Comparator是一个比较器，是一种工具，它里面有两个方法：int compare（T o1，T2 o2）;boolean equals(Object object);
Comparable里面有一个方法：int compareTo(T o)；
它们都是接口，Comparable里面的那个方法只能比较实现了这个方法本身的类，但只要具有可比性的类都可以用实现了Comparator这个接口里面的方法进行比较！
Comparable 是一个对象本身就已经支持自比较所需要实现的接口；而 Comparator 是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。
分享到：
相关推荐
数据结构优先队列，是一个简易版优先队列，输入数据及权值可以对其进行插入，删除等操作。
本文实例讲述了JavaScript数据结构之优先队列与循环队列。分享给大家供大家参考，具体如下： 优先队列 实现一个优先队列：设置优先级，然后在正确的位置添加元素。 我们这里实现的是最小优先队列，优先级的值小...
对数据结构中优先队列的设计，这个仅是参考。
7. 特殊类型的队列：优先队列（Priority Queue），用于处理具有优先级的元素，如最小堆实现。 8. 双端队列（Deque，Double-ended Queue）：支持在两端进行插入和删除操作，常用于实现滑动窗口最大值等算法。 在学习...
在C语言中实现优先队列，通常会选择使用堆数据结构，因为它可以保证插入、删除和查找操作的时间复杂度为O(logn)，其中n是队列中的元素数量。堆是一种近似完全二叉树的结构，可以分为大顶堆和小顶堆。小顶堆的性质是...
在数据结构课程设计中，优先队列数据类型（priority_queue）是核心概念之一，常用于实现高效的调度、搜索和优化问题。在本项目中，我们将讨论如何实现这种数据结构以及其主要操作。 **一、优先队列的定义** 优先...
数据结构栈和队列解决迷宫问题 本文档详细介绍了利用栈和队列解决迷宫问题的步骤，对于初学者学习数据结构能很好的进行辅导。本文档主要涉及到数据结构的两个重要概念：栈和队列，并介绍了如何使用这两个数据结构来...
数据结构 基于链表实现的优先队列 Cpp文件
优先队列是一种特殊的数据结构，它允许我们按照优先级顺序处理元素。在计算机科学中，尤其是在算法和数据结构领域，优先队列常用于解决需要快速访问最高优先级元素的问题，如Dijkstra算法或Prim算法。在C语言中，...
优先队列是一种特殊的数据结构，它允许用户以特定的优先级进行元素的插入和删除操作。在MATLAB中实现优先队列，可以帮助我们处理需要快速访问最高优先级元素的问题，例如在任务调度、图形渲染或者搜索算法中。...
在众多的数据结构中，队列是一种基础且重要的结构，尤其在处理任务调度、消息传递等场景中有着广泛的应用。本项目是关于数据结构中队列的实现，使用C++编程语言进行开发。 队列是一种线性数据结构，遵循“先进先出...
优先队列在Java编程中是一种特殊的数据结构，它遵循特定的出队顺序，通常是最小元素（最小优先队列）或最大元素（最大优先队列）先出队。这种数据结构在解决各种问题时非常有用，例如任务调度、事件驱动编程、搜索...
优先队列是一种特殊的数据结构，它支持两种主要的操作：插入元素和删除最小（或最大）元素。在实际应用中，优先队列常用于任务调度、事件驱动模拟以及各种排序算法等场景。 ### 二、优先队列的实现 #### 1. 数据...
本主题关注的是如何使用C语言来实现数据结构中的栈和队列，这是两种基础但非常重要的抽象数据类型（ADT）。 栈（Stack）是具有后进先出（LIFO）特性的数据结构。它类似于一个堆叠的盘子，最新的元素被放在顶部，...
总之，`PriorityQ.java`文件可能是一个简单的数组实现优先队列的示例，通过分析这个文件，我们可以学习到如何利用数组数据结构实现优先队列，以及理解其核心的插入、删除和查找操作。同时，这也能帮助我们更好地掌握...
优先队列的数据结构由两个部分组成：元素数组和队列信息。元素数组用于存储优先队列中的元素，每个元素由数据和优先权值组成。队列信息包括队列的长度、队列的已分配存储空间大小和队列的当前元素个数。 知识点三：...
综上所述，这个“简单的优先队列”主题涵盖了许多基础数据结构和算法，包括平衡树、背包策略、图的表示以及队列接口。通过理解和应用这些知识，我们可以设计和实现高效的优先级队列系统，用于解决各种实际问题。
优先队列是一种特殊的数据结构，它允许我们按照优先级顺序处理元素。在计算机科学中，尤其是在算法设计中，优先队列常被用于解决各种问题，如任务调度、事件驱动模拟和图形学等。本实现是用Java编程语言完成的，Java...