最大-最小堆

 这篇文章可以证实是由NOCOW用户原创，不存在任何版权争议。
 本文作者同意以GNU FDL、CC-by-sa和GNU LGPL（如果适用）三种版权发布此文章（不包括翻译文章中属于原始所有者的部分版权）。
 如果你修改了这篇文章并且不同意用GNU FDL以外的版权发布，可以换一个版权模板或者移除此模板。

介绍

最大堆和最小堆是二叉堆的两种形式。

1. 最大堆：根结点的键值是所有堆结点键值中最大者的堆。
2. 最小堆：根结点的键值是所有堆结点键值中最小者的堆。

而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。

最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。

以最大（小）层结n点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

主要操作

不失一般性，只讨论根结点为最小层的情况。

插入

   void insert(int x);

弹出

   void pop(int &x);

擦

代码

 
struct heap{
    int size;
    int a[11000];
    heap(){size=0;}
    void insert(int x){
         int p;
         for(p=++size;p>1&&a[p>>1]>x;a[p]=a[p>>1],p>>=1);
         a[p]=x;
         }
    void pop(int &x){
         int p,c;
         for(x=a[p=1],c=2;c<size&&(a[c+=(c+1<size&&a[c+1]<a[c])?1:0]<a[size]);a[p]=a[c],p=c,c<<=1);
         a[p]=a[size--];
         }
    }h;

应用

双端优先队列

最大-最小堆是一个小作品，欢迎帮助扩充这个条目。