STL 最大堆与最小堆

时间:2022-06-30 17:37:53

  在第一场CCCC选拔赛上,有一关于系统调度的水题。利用优先队列很容易AC。

  // 由于比赛时花费了不少时间研究如何定义priority_queue的比较函数,决心把STL熟练掌握...

  

Queue

  首先来看http://www.cplusplus.com/reference/queue/queue/对STL Queue容器的介绍。

  在C++中只要#include<queue>可使用队列类,常用的成员函数有

1. push

2. pop

3. size

4. empty

5. front

6. back     // 目前还没使用过,留意一下

  队列在BFS时经常使用,已经比较熟悉其用法。

 

Priority_queue

  在CPP网站上同样也有优先队列的详细介绍。在《数据结构与算法分析》一书上,堆(heap)等同于优先队列,或者准确地说,优先队列是通过堆实现的。

  相比队列,priority_queue的成员函数名基本一致,除了将front改为top,都是获取队首元素。

1. push

2. pop

3. size

4. empty

5. top

priority_queue<int, vector<int>, greater<int> > q;  // 小顶堆  
priority_queue<int, vector<int>, less<int> > q;     // 大顶堆,默认  

// 自定义数据结构
// 方式一
struct Node{  
    int x, y;  
    Node(int a = 0, int b= 0):x(a), y(b) {}  
};  
   
struct cmp{  
    bool operator() (const Node& a, const Node& b ){  
        if (a.x == b.x)   
            return a.y > b.y;  
        return a.x > b.x;   
    }  
};  

priority_queue<Node, vector<Node>, cmp> q;

// 方式二
struct Node{  
    int x, y;  
    Node(int a = 0, int b= 0):x(a), y(b) {}  
};  
  
bool operator < (const Node& a, const Node& b ){  
    if (a.x == b.x)   
        return a.y > b.y;  
    return a.x > b.x;   
}  

   上次比赛时,我忘了如何加上vector<int>部分,摸索半天通过方式二(编写的友元函数实现)才成功调试好代码,浪费了大量的时间。希望以后能记牢,平常多加练习达到熟练运用的水平^_^

 

STL 堆操作

  // 参考COPY自https://blog.csdn.net/my_lovely_lemon_tree/article/details/78007316 

  头文件是#include <algorithm>
  一般用到这四个:make_heap()、pop_heap()、push_heap()、sort_heap();
  (1)make_heap()构造堆
  void make_heap(first_pointer,end_pointer,compare_function);
  默认比较函数是(<),即最大堆。
  函数的作用是将[begin,end)内的元素处理成堆的结构

  (2)push_heap()添加元素到堆
  void push_heap(first_pointer,end_pointer,compare_function);
  新添加一个元素在末尾,然后重新调整堆序。该算法必须是在一个已经满足堆序的条件下。
  先在vector的末尾添加元素,再调用push_heap

  (3)pop_heap()从堆中移出元素
  void pop_heap(first_pointer,end_pointer,compare_function);
  把堆顶元素取出来,放到了数组或者是vector的末尾。
  要取走,则可以使用底部容器(vector)提供的pop_back()函数。
  先调用pop_heap再从vector中pop_back元素

  (4)sort_heap()对整个堆排序
  排序之后的元素就不再是一个合法的堆了。