数据结构之优先队列

92 阅读 0 评论 61 点赞

我是靠谱客的博主愤怒樱桃，最近开发中收集的这篇文章主要介绍数据结构之优先队列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

    这几天查阅了一些关于优先队列的资料，记得我们用优先队列的时候也是在做那个哈弗曼编码的时候，计算每个字符出现的频率之后，再将出现次数越多的就放在靠近树根越近的位置，就在这里用到了优先队列，刚开始真的不懂优先队列是干嘛的，不晓得为什么要存在这么一个东西，搞得自己好茫然的，后来看了源代码什么的之后，才发现它是这么简单！
    在这之前我们都了解了一些有关于队列的知识，优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。优先队列也是要涉及到查找和排序的一类数据结构：
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 是一个专用的比较器，当这个对象不支持自比较或者自比较函数不能满足你的要求时，你可以写一个比较器来完成两个对象之间大小的比较。