堆

Posted on Edited on

优先级队列：

按照事先约定的优先级，可以始终高效查找并访问优先级最高数据项的数据结构

维护了数据项的一个偏序关系

操作接口

1
2
3
4
5
6
7
8
size(); //报告优先级队列的规模

 insert(); //将指定词条插入优先级队列
   
    
 getMax();
    
 delMax(); //删除优先级最大的词条

应用实例:Huffman编码树，堆

Huffman编码树：略

堆

原理：

​ 主要求解问题：O(1)的算法在n个给定的整数中找最大值, 有限偏序集的极值必然存在，堆用来维护一个偏序关系

性质：

​ 1.完全二叉树

​ 2.保存有序关系. 小根堆:每个结点的值都小于其子结点的值;

​ 大根堆: 每个结点的值都大于其子结点的值;

物理结构:

​ 有序列表

主要操作:

​ ==上浮操作== —当大根堆的元素变大时，该结点可能会==上浮== —O(log n)

1
2
3
4
5
6
7
inline void up(int index){ //处于index的元素变大
    int i=index;
    while( i>1 && h[i]>h[i/1]){//对于大根堆来说，如果子结点大于父结点，一定需要交换
        swap(h[i],h[i/2]);
        i>>1;
    }
}

​ ==下沉操作==—当大根堆的元素变小时，该结点可能会==下沉== —-O(log n)

1
2
3
4
5
6
7
8
9
10
11
12
inline void down(int index){
    int i=index;
    while( (2*i<= len &&  h[2*i] > h[i]) ||
         (2*i+1<=len && h[2*i+1] > h[i])  ) {
        	int temp = 2*i;         //temp用于保存 较大的元素的下标
       		if( h[2*i+1] > h[i] ){
            	temp++; //temp为2*i+1
        	}
    	swap(h[index], h[temp]);
        i=temp ;//判断是否需要继续下沉
    }
}

​ ==插入操作==–O(log n)–在数组最末尾插入元素,再做up操作

1
2
3
4
5
inline void insert(int x){ //插入x
	len++;
	h[len] = x;
	up(len);
}

​ ==删除操作==–O(log n)–删除第index个元素，为了不破坏堆的性质，把h[len]移动到index处，堆元素个数减一，再判断做up(index) 还是down(index)

1
2
3
4
5
6
7
8
9
10
inline void delete(index ){
    int t=h[index];
    h[index]=h[len];
    len--;
    if( h[index] >t ) 
        up(index);
    else
        down(index);
    return t;
}

过程: 初始建堆

​ 方法1：执行n次insert操作,时间复杂度O(n*log n)

1
2
3
4
void build(){
	for(int i=1; i<=n;i++)
		insert(a[i]);
}

​ 方法2：执行n/2次down操作 

1
2
3
4
5
6
void build(){
    len = n;
    for(int i=1;i<n;i++) h[i]=a[i];
    for(int i=n/2;i>=1;i--) down(i);
}

堆排序

初始建堆 O(n),堆排序算法为 O(n log n)

时间复杂度：最好，最坏，平均情况相同

1
2
3
4
5
6
7
8
9
10
void HeapSort(){
	//初始建堆
    build();
    //堆排序
    for(int i=1;i<n-1;i++){
        swap(1,hlen);
        hlen--;
        down(1); //不断删除最大结点
    }
}

(小根堆相反)

STL中堆的使用

方法1：<queue>中的priority_que

初始化方式
1
2
template<typename T, typename Container=std::vector<T>,typename Compare=std::less<T> >
class priority_queue
基本操作
1
2
3
4
5
6
7
8
9
10
11
push(const T& obj);// 将obj的副本放到容器的适当位置，这通常会包含一个排序操作。

push(T& obj); //将obj放到容器的适当位置，这通常会包含一个排序操作。

emplace(T constructor a rgs...);
//通过调用传入参数的构造函数，在序列的适当位置构造一个T对象。为了维持优先顺序，通常需要一个排序操作。
top();//：返回优先级队列中第一个元素的引用。
pop();//：移除第一个元素。
size();//：返回队列中元素的个数。
empty()//：如果队列为空的话，返回true。
swap(priority_queue<T>& other);//：和参数的元素进行交换，所包含对象的类型必须相同。
使用

1.最基本的使用方法，对于一串数字建堆（默认为大根堆）

1
priority_queue<int> heap;

2.自定义

1
2
3
priority_queue<int,vector<int>, greater<int> > qi2;//最小堆

priority_queue<int,vector<int>, less<int> >qi3; //最大堆

  • 使用自定义的cmp类，重载operator

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    struct Node{
    	int x;
        int y;
        int val;
       Node(int a,int b,int valin):x(a),y(b),val(valin){}
    };

    struct cmp{
        bool operator()(const Node& a, const Node& b){
            return a.val<b.val;//大根堆
        }
    }

    priority_queue<Node,vector<Node>, cmp> heap;//建堆
    heap.pop();//出堆
    heap.push();//入堆
    heap.top(); //获取堆顶元素

方法2：利用vector

这种法法需要#include<algorithm> #include <functional>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> a;
//建堆
make_heap(a.begin(),a.end(), less<int>() );//最大堆
make_heap(a.begin(),a.end(), greater<int>() );//最小堆
//pop
pop_heap(a.begin(),a.end(), less<int>() );//最大值出堆
pop_heap(a.begin(),a.end(), less<int>() );//最小值出堆


//插入元素
push_heap(a.begin(),a.end(),cmp);
//堆排序

sort_heap(a.begin(),a.end(),cmp);
// push_heap ( begin , end )   将最后一个元素插入堆中（堆自动调整）
// pop_heap ( begin , end )   将第一个元素从堆中删去（堆自动调整），并放到最后
// find ( begin , end , value ) 从begin到end查找value，若找不到，返回end