堆结构是一种数组对象，是一棵完全二叉树。

为红河等地区用户提供了全套网页设计制作服务，及红河网站建设行业解决方案。主营业务为成都做网站、成都网站制作、红河网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

性质

若当前节点编号为i，父结点则为i/2，左孩子为2i，右孩子为2i+1。

堆的结点数\(\le\)数组长度len

下图为一个大根堆：每个结点均小于其父结点，树根是堆中最大的结点，小根堆反之。

添加

往堆中添加一个元素。

重复n次添加操作，即可建立一个小根堆。

实现流程（以小根堆为例）

先在堆尾加入1个元素,并把这个结点置为当前结点。

比较当前结点和它的父结点的大小，

如果当前结点小于父结点，交换它们的值，把父结点置为当前结点。

重复以上过程。

如果当前结点大于等于父结点，结束。

取出堆顶

从堆中取出并删除一个元素。

实现流程（以小根堆为例）

取出根结点的值。

把堆的最后一个结点(len)放到根的位置上，把根覆盖掉。

把堆的长度减一。

把根结点置为当前结点。

如果当前节点无儿子（pa>len/2），结束。

否则，比较当前节点与其子节点的值，

如果当前节点的值小于等于其子节点，结束。

反之则交换这两个结点的值，重复上述步骤，直至结束。

优先队列

priority_queue

Type是数据类型，Container是容器类型。

（Container必须是用数组实现的容器，比如vector,deque等，但不能用list，STL里默认用vector）

Functional是比较函数，当需要用自定义的数据类型时才需要传入这三个参数，使用基本数据类型时，只需要传入数据类型，默认是大根堆。

头文件

include

定义小根堆

priority_queue,greater>q;//升序队列

定义大根堆

priority_queue,less>q;//降序队列

基本操作

empty()

如果队列为空，则返回真。

pop()

删除队头元素，即删除第一个元素。

push(）

加入一个元素。

size()

返回优先队列中拥有的元素个数。

top()

返回优先队列队头元素，即优先级最高的元素。

在默认的优先队列中，优先级高的先出队。

在默认的int型中先出队的为较大的数。

堆排序

并非原创，仅是整理，请见谅

网站名称：堆
标题路径：http://www.cdkjz.cn/article/dsoipos.html