堆和优先队列

• 1.堆
  • 1.1关键操作
  • 1.2 STL heap
• 2.优先队列

1.堆

从结构上来说是一种完全二叉树(假设树有n层，前n-1层元素塞满，第n层所有元素靠着左边)

根据排序方式分为最大堆和最小堆。最大堆定义是父节点比它的子节点要大

1.1关键操作

堆主要有两种关键的操作

1.1.1插入

将新插入的元素放入二叉树的最下最右位置，然后循环不断和它的父节点进行比较，假设最大堆，如果比父节点大，交换位置，继续和当前的新父节点比较，直到小于父节点位置。
操作图如下：

1.1.2删除

删除二叉树最顶段节点后，关键是如何安排最后一个节点。首先，将最后一个节点放入最顶端，然后和两子节点进行比较，如果子节点大于当前节点，和最大的子节点进行交换。不断循环这个操作，直到新节点比两个子节点都更大。
操作图如下

1.1.3创建

对于二叉树[first，last）
首先对最后一个元素last-1，不断比较它和它的父节点并交换，将它放入正确的位置。然后判断位置last-2的元素，重复这个操作。
关键操作放入正确位置，参考插入操作。

---

1.2 STL heap

在stl中并没有将heap作为一种底层容器，heap的实现亦需要更低一层的容器组件（诸如list,array,vector）作为其底层机制。Heap是一个类属算法，包含在algorithm头文件中。
常见有四个操作：make_heap,push_heap,pop_heap,sort_heap.
以下四个操作可以自主提供比较函数，也可以省略采用系统自带less，为最大堆。不再重复说明。
以下函数全是左闭右开[first,end)

• make_heap

void make_heap(first_pointer,end_pointer,compare_function);
void make_heap(first_pointer,end_pointer);

对[first,end)元素创建一个堆

• push_heap

void push_heap(first_pointer,end_pointer,compare_function);
void push_heap(first_pointer,end_pointer);

push_heap()假设由[first,end-1)是一个有效的堆，然后，再把堆中的新元素加进来，做成一个堆

• pop_heap

void pop_heap(first_pointer,end_pointer,compare_function);
void pop_heap(first_pointer,end_pointer);

默认[first,end)是堆结构,注意：pop_heap之后，原先二叉树最顶上元素只是被置于底部容器的最尾端，尚未被取走

• sort_heap

void sort_heap(first_pointer,end_pointer);
void sort_heap(first_pointer,end_pointer,compare_function);

循环调用pop_heap，将顶部元素一段放入
//作用是sort_heap对[first,end)中的序列进行排序。它假设这个序列是有效堆。
//默认为最大堆，进行sort_heap得到递增序列。

---

2.优先队列

优先队列是个具有权值概念的队列，随意顺序入队，出队时按照权值顺序出队。

priority_queue默认以vector作为底层容易，再加上heap处理规则。所以实现很简单。

template <class T,class Sequence = vector<T>,class Compare=less<typename Sequence::value_type>>
class priority_queue{
    Sequence c;//底层容易
    Compare cmp;//比较函数

    priority_queue(){c();}

    bool empty(){return c.empty();}

    Sequence::const_reference top()const{return c.front();}

    priority_queue(InputerIterator first,InputerIterator end,const compare &x):c(first,last),cmp(x)
    {
        make_heap(c.begin(),c.end(),cmp);
    }
    //等等
}

• 构造函数

//定义比较结构
struct cmp{
    bool operator ()(int &a,int &b){
        return a>b;//最小值优先
    }
};

//自定义数据结构
struct number{
    int x;
    bool operator < (const number1 &a) const {
        return x>a.x;//最小值优先
    }
};

    priority_queue<int,vector<int>,cmp>que1;//最小值优先
    priority_queue<number>que5; //最小优先级队列    

• push
• pop
• top
• size
• empty