浅谈堆与优先队列

Posted on | In | Visitors:

堆

概述

如果有一个关键码集合K={k0,k1,k2,…kn-1}，把它们所有的元素按照完全二叉树的顺序存储方式存放在一个一维数组中。并且满足：
ki<=k(2i+1)且ki<=k(2i+2) （或者ki>=k(2i+1)且ki>=k(2i+2)） i=0,1,2…(n-2)/2
则称这个集合为小根堆（或大根堆）。即小根堆的双亲结点值不大于孩子结点值，根结点最小；大根堆反之。下面均由小根堆来说明问题，大根堆类似。

结构定义：

1
2
3
4
5
6
#define heapSize 40
typedef int HElemType;
typedef struct{
    HElemType elem[heapSize];    //堆元素存储数组
    int curSize;    //堆当前元素个数
}minHeap;

一维数组elem是完全二叉树的顺序存储，由完全二叉树的性质5，给定任意结点i（从0开始），查找其双亲和左右子女的方法为：

  1. 如果i=0，结点i是根结点，无双亲；否则结点i的双亲为floor((i-1)/2)。
  2. 如果2i+1>n-1，则结点i没有左子女；否则结点i的左子女为结点2i+1。
  3. 如果2i+2>n-1，则结点i没有右子女，否则结点i的右子女为结点2i+2。

实现

堆的建立
从离根最远的非叶结点开始，先把它们调整为小根堆，再以它们为基础，把更上层的子树调整为小根堆。由于子树的根下属的子树都已经是小根堆，只需从它开始向下调整就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void siftDown(minHeap &H,int start,int m){
    int i = start;
    HElemType temp = H.elem[i];
    for(int j = 2*i+1;j<m;j = j*2+1){
        if(j<m && H.elem[j]>H.elem[j+1])
            j++;
        if(temp<H.elem[j])
            break;
        H.elem[i] = H.elem[j];
        i = j;
    }
    H.elem[i] = temp;
}
void createMinHeap(minHeap &H,ElemType arr[],int n){
    int i;
    for(i = 0;i<n;i++){
        H.elem[i] = arr[i];
    }
    H.curSize = n;
    for(i = (H.curSize-2)/2;i>=0;i--){
        siftDown(H,i,H.cureSize-1);
    }
}

堆的插入
堆的插入算法调用了另一种堆的调整方法siftUp，实现自下而上的调整。因为每次新结点总是插在已经建成的堆的后面。这时需要从下向上，与双亲的关键码进行比较，对调。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void siftUp(minHeap &H,int start){
//从结点start开始到结点0为止，自下向上比较，如果子女值小于双亲的值，则双亲的值下降，
//再用子女的值继续向上层比较，这样将集合重新调整为堆
    HElemType temp = H.elem[start];
    int j = start;
    int i = (j-1)/2;
    while(j>0){
        if(H.elem[i] <= temp)    //双亲的值小，不做调整
            break;
        else{
            H.elem[j] = H.elem[i];
            j = i;
            i = (j-1)/2;
         }
    }
    H.elem[j] = temp;
}
int Insert(minHeap &H,HElemType x){
    if(H.curSize == heapSize)
        return 0;    //堆满，插入失败
    H.elem[curSize] = x;
    siftUp(H,H.curSize);
    curSize++;
    return 1;
}

堆的删除
通常堆的删除即将堆顶元素删除，一般以堆的最后一个结点填补取走的堆顶元素，然后自顶向下调整。

1
2
3
4
5
6
7
8
9
10
int Remove(minHeap &H,DataType &x){
    if(H.curSize == 0){
        return 0;
    }
    x = H.elem[0];
    H.elem[0] = H.elem[H.curSize-1];
    H.curSize--;
    siftDown(H,0,H.curSize-1);
    return 1;
}

优先队列

priority_queue是一个拥有权值观念的queue，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列。缺省情况下priority_queue利用一个大根堆实现，权值最高者排在最前面

priority_queue的所有元素，进出都有一定打得规则，只有queue顶端的元素（权值最高者），才有机会被外界取用。priority_queue不提供遍历功能，也不提供迭代器。

具体优先队列的描述可以见本人另一篇博客

下面说一下改变优先级的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>  
#include<queue>  
#include<cstdlib>  
using namespace std;  
struct Node{  
    int x,y;  
    Node(int a=0, int b=0):  
        x(a), y(b) {}  
};  
  
struct cmp{  
    bool operator()(Node a, Node b){  
    	//优先按照x从小到大排，若x相等，按y从小到大。勿反！！！
        if(a.x == b.x)  return a.y>b.y;  	
        return a.x>b.x;  
    }  
};  
  
int main(){  
    priority_queue<Node, vector<Node>, cmp>p;  
      
    for(int i=0; i<10; ++i)  
        p.push(Node(rand(), rand()));  
          
    while(!p.empty()){  
        cout<<p.top().x<<' '<<p.top().y<<endl;  
        p.pop();  
    } 
    return 0;  
}

参考资料：
《数据结构——殷人昆》
《STL源码剖析》