数据结构——优先队列和堆
2018-07-16 本文已影响16人
我哈啊哈啊哈
目录
1、优先队列
1.1、什么是优先队列
1.2、优先队列的实现
2、堆
2.1、什么是堆
2.2、堆的类型
2.3、二叉堆
2.3.1、堆的声明
2.3.2、创建堆
2.3.3、结点的双亲
2.3.4、结点的孩子
2.3.5、获取最大元素
2.3.6、堆化元素
2.3.7、删除元素
2.3.8、插入元素
2.3.9、清空堆
2.3.10、数组建堆
2.3.11、堆排序
正文
1、优先队列
1.1、什么是优先队列
-
为了找到元素集合中的最小或最大元素，优先队列支持插入（Insert）删除最小值（DeleteMin）操作（返回并删除最小元素）或删除最大值（DeleteMax）操作（返回并删除最大元素）。如图1-1所示。
图1-1 优先队列示例
- 如果最小键值元素拥有最高的优先级，那么这种优先队列叫做升序优先队列（即总是删除最小的元素）。类似地，如果最大键值元素拥有最高的优先级，那么这种优先队列叫做降序优先队列（即总是删除最大的元素）。
1.2、优先队列的实现
- 首先列出可其可能的实现方式。
1）无序数组实现：将元素插入数组中，不考虑元素的顺序，则插入的时间复杂度为O(1)，删除操作需要找到相应的键值，然后进行删除，则删除的时间复杂度为O(n)。
2）无序链表实现：类似数组实现，插入的时间复杂度为O(1)，删除的时间复杂度为O(n)。
3）有序数组实现：元素按照键值排序的方式插入数组中，插入的时间复杂度为O(n)，删除只在数组一端执行，则删除的时间复杂度为O(1)。
4）有序链表实现：元素按照键值排序的方式插入链表中，与数组类似，插入的时间复杂度为O(n)，删除只在数组一端执行，则删除的时间复杂度为O(1)。
5）二叉搜索树实现：若随机插入元素，则插入和删除操作的平均时间复杂度为O(logn)。
6）平衡二叉搜索树实现：插入和删除操作的平均时间复杂度为O(logn)。
7）二叉堆实现：在第2节中会说明堆实现的细节。二叉堆实现搜索、插入和删除的时间复杂度均为O(logn)，而找到最大或最小元素的时间复杂度均为O(1)。 -
上述实现的比较如图1-2所示。
图1-2 实现比较
2、堆
2.1、什么是堆
-
堆是一棵具有特定性质的二叉树。基本要求是堆中所有结点的值必须大于等于（或者小于等于）其孩子结点的值。如图2-1所示。
图2-1 堆
2.2、堆的类型
-
最小堆：结点的值必须小于或等于其孩子结点的值。如图2-2所示。
图2-2 最小堆
-
最大堆：结点的值必须大于或等于其孩子结点的值。如图2-3所示。
图2-3 最大堆
2.3、二叉堆
-
在二叉堆中，每个结点最多有两个孩子结点，也就是在形式上是一棵完全二叉树，所以用数组来存储二叉堆不会浪费任何空间。假定所有元素都存储在数组中，从下标0开始。图2-3可以表示成如图2-4所示。
图2-4 数组表示
2.3.1、堆的声明
/**
* @Auther: lalala
* @Date: 2018/7/15 15:08
* @Description:二叉堆
*/
public class Heap {
public int[] array;
public int count; //堆的元素个数
public int capaticy; //堆的大小
public int heap_type; //最小堆或最大堆
public Heap(int capaticy,int heap_type){
//具体实现如下
}
public int Parent(int i){
//具体实现如下
return -1;
}
public int LeftChild(int i){
//具体实现如下
return -1;
}
public int RightChild(int i){
//具体实现如下
return -1;
}
public int GetMaximum(){
//具体实现如下
return -1;
}
}
2.3.2、创建堆
public Heap(int capaticy,int heap_type){
this.heap_type=heap_type;
this.count=0;
this.capaticy=capaticy;
this.array=new int[capaticy];
}
2.3.3、结点的双亲
- 对于第i个位置上的结点，其双亲结点在（i-1）/2位置上。图2-3中，结点6在2号位置，其双亲结点在0号位置。
public int Parent(int i){
if(i<=0||i>this.count){
return -1;
}
return (i-1)/2;
}
2.3.4、结点的孩子
- 第i个位置结点的孩子处在2i+1和2i+2位置上。如图2-3中，结点6在2号位置，它的孩子结点2和5，分别处在5和6号位置上。
public int LeftChild(int i){
int left=2*i+1;
if(left>this.count){
return -1;
}else {
return left;
}
}
public int RightChild(int i){
int right=2*i+2;
if(right>this.count){
return -1;
}else {
return right;
}
}
2.3.5、获取最大元素
- 该例子为最大堆，所以最大元素位于根结点，也就是数组的0号位置。
public int GetMaximum(){
if(this.count==0){
return -1;
}else {
return this.array[0];
}
}
2.3.6、堆化元素
-
当插入一个元素到堆中时，它可能不满足堆的性质，这种情况下需要调整堆中的位置使之重新变为堆，这个过程叫做堆化。如图2-5所示，需要进行堆化。
图2-5 示例
-
为了堆化结点1，先找到它孩子结点中的最大值，然后交换它们的位置。如图2-6所示。
图2-6 示例（2）
-
持续这个过程，现在交换1和8。如图2-7所示。
图2-7 示例（3）
- 代码实现如下：
public void PercolateDown(int i){
int l,r,max,temp;
l=LeftChild(i);
r=RightChild(i);
if(l!=-1&&this.array[l]>this.array[i]){
max=l;
}else {
max=i;
}
if(r!=-1&&this.array[r]>this.array[max]){
max=r;
}
if(max!=i){
temp=this.array[i];
this.array[i]=this.array[max];
this.array[max]=temp;
}
PercolateDown(max);
}
2.3.7、删除元素
- 为了从堆中删除元素，只需从根结点删除元素。当删除根结点后，将堆中最后一个元素复制到这个位置，然后删除最后的元素。可能会导致不满足堆的性质，为了使其再次成为堆，需要调用上述函数PercolateDown。
1）、将第一个元素复制到其他变量。
2）、将最后一个元素复制到第一个元素位置。
3）、PercolateDown（第一个元素）。
public int DeleteMax(){
if(this.count==0){
return -1;
}
int data=this.array[0];
this.array[0]=this.array[count-1];
this.count--;
PercolateDown(0);
return data;
}
2.3.8、插入元素
- 类似堆化和删除过程
1）、堆的大小加1。
2）、将新元素放在堆的尾部。
3）、从下置上堆化这个元素。
public int Insert(int data){
int i;
if(this.count==this.capaticy){
ResizeHeap();
}
this.count++;
i=this.count-1;
while (i>=0&&data>this.array[(i-1)/2]){
this.array[i]=this.array[(i-1)/2];
i=(i-1)/2;
}
this.array[i]=data;
return i;
}
public void ResizeHeap(){
int[] array_old=new int[this.capaticy];
System.arraycopy(this.array,0,array_old,0,this.count-1);
this.array=new int[this.capaticy*2];
if(this.array==null){
return;
}
for(int i=0;i<this.capaticy;i++){
this.array[i]=array_old[i];
}
this.capaticy*=2;
array_old=null;
}
2.3.9、清空堆
public void DestroyHeap(){
this.count=0;
this.array=null;
}
2.3.10、数组建堆
public void BuildHeap(Heap h,int[] A,int n ){
if(h==null){
return;
}
while (n>h.capaticy){
h.ResizeHeap();
}
for(int i=0;i<n;i++){
h.array[i]=A[i];
}
h.count=n;
for(int i=(n-1)/2;i>=0;i--){
h.PercolateDown(i);
}
}
2.3.11、堆排序
public void Heapsort(int[] A,int n){
Heap h=new Heap(n,0);
int old_size,i,temp;
BuildHeap(h,A,n);
old_size=h.count;
for(i=n-1;i>0;i--){
//h.array[0]存储最大元素
temp=h.array[0];
h.array[0]=h.array[h.count-1];
h.count--;
h.PercolateDown(i);
}
h.count=old_size;
}
