特殊的完全二叉树堆（神奇的队列优化）

满二叉树&＃xff1a;高度为h&＃xff0c;结点数为2*h-1。
完全二叉树&＃xff1a;高度为h&＃xff0c;1~h-1层结点数满&＃xff0c;第h层从右到左缺若干结点。若有N个结点&＃xff0c;高度为log2N。

最小堆&＃xff1a;在完全二叉树的基础上&＃xff0c;所有的父结点都比子结点小。
最大堆&＃xff1a;在完全二叉树的基础上&＃xff0c;所有的父结点都比子结点大。

问题引入&＃xff1a;14个数&＃xff1a;99 5 36 7 22 17 46 12 2 19 25 28 1 92&＃xff0c;若删除其中最小的元素&＃xff0c;并新增k&＃xff0c;重复14次
普通的数组遍历&＃xff1a;O(n*n)

引入最小堆&＃xff1a;
将14个树构造最小堆&＃xff0c;用h数组存储&＃xff0c;h[1]就是最小的。
将堆顶删除&＃xff0c;把k放入堆顶&＃xff0c;向下调整&＃xff0c;重新构造出最小堆。O(logN)

向下调整&＃xff1a;

void swap(int x,int y)
{int t;t&＃61;h[x];h[x]&＃61;h[y];h[y]&＃61;t;
}
void siftdown(int i)/*传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点向下调整*/
{int t,flag&＃61;0;/*flag用来标记是否需要继续向下调整*/while(i*2<&＃61;n&&flag&＃61;&＃61;0)/*当i结点有儿子(其实是至少有左儿子的情况下)并且有需要继续调整的时候,循环就执行*/{if(h[i]>h[i*2])/*首先判断它和左儿子的关系,并用t记录值较小的结点编号*/t&＃61;i*2;elset&＃61;i;if(i*2&＃43;1<&＃61;n)/*右儿子存在,再对右儿子进行讨论*/{if(h[t]>h[i*2&＃43;1])t&＃61;i*2&＃43;1;}if(t!&＃61;i)/*最小的结点不是自己,说明子结点中有比父结点更小的*/{swap(t,i);i&＃61;t;/*更新i为刚才与它交换的儿子结点的编号*/}elseflag&＃61;1;/*父结点已经比两个子结点都小,不需要再进行调整*/}
}

若新增一个数&＃xff0c;插入到末尾&＃xff0c;向上调整&＃xff0c;使其符合最小堆的特性。

向上调整&＃xff1a;

void siftup(int i)/*传入一个需要向上调整的结点编号i*/
{int flag&＃61;0;/*标记是否需要继续向上调整*/if(i&＃61;&＃61;1)/*堆顶*/return;while(i!&＃61;1&&flag&＃61;&＃61;0){if(h[i]<h[i/2])swap(i,i/2);/*交换它和它爸爸的位置*/elseflag&＃61;1;i&＃61;i/2;/*更新编号i为它父结点的编号*/}
}

如何建立堆&＃xff1f;

用数组h存储&＃xff0c;把n个数放入完全二叉树中&＃xff0c;即放入数组中。
从最后一个节点开始&＃xff0c;依次判断以这个结点为根的子树是否满足堆的特性。
若所有的子树都满足堆&＃xff0c;那么这个完全二叉树就是最小堆或最大堆。
以叶结点为根的子树其实就是叶结点自己&＃xff0c;可以不考虑叶结点。O(N)

二叉树的性质&＃xff1a;最后一个非叶结点的编号是N/2。
所以可以从第N/2个结点开始。

建堆及其堆排序(建立最小堆)&＃xff1a;

#include
#include
#include
using namespace std;
int h[101];
int n;/*堆的大小*/
void swap(int x,int y)
{int t;t&＃61;h[x];h[x]&＃61;h[y];h[y]&＃61;t;
}
void siftdown(int i)/*传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点向下调整*/
{int t,flag&＃61;0;/*flag用来标记是否需要继续向下调整*/while(i*2<&＃61;n&&flag&＃61;&＃61;0)/*当i结点有儿子(其实是至少有左儿子的情况下)并且有需要继续调整的时候,循环就执行*/{if(h[i]>h[i*2])/*首先判断它和左儿子的关系,并用t记录值较小的结点编号*/t&＃61;i*2;elset&＃61;i;if(i*2&＃43;1<&＃61;n)/*右儿子存在,再对右儿子进行讨论*/{if(h[t]>h[i*2&＃43;1])t&＃61;i*2&＃43;1;}if(t!&＃61;i)/*最小的结点不是自己,说明子结点中有比父结点更小的*/{swap(t,i);i&＃61;t;/*更新i为刚才与它交换的儿子结点的编号*/}elseflag&＃61;1;/*父结点已经比两个子结点都小,不需要再进行调整*/}
}
void creat()
{int i;for(int i&＃61;n/2; i>&＃61;1; i--) /*从最后一个非叶结点到第1个结点依次进行向上调整*/siftdown(i);
}
int deletemax()
{int t;t&＃61;h[1];/*记录堆顶点的值*/h[1]&＃61;h[n];/*将堆的最后一个点赋值到堆顶*/n--;/*堆元素减少1*/siftdown(1);/*调整*/return t;
}
int main()
{int i,num;scanf("%d",&num);for(int i&＃61;1; i<&＃61;num; i&＃43;&＃43;)scanf("%d",&h[i]);n&＃61;num;creat();/*建堆*/for(int i&＃61;1; i<&＃61;num; i&＃43;&＃43;) /*删除顶部元素,连续删除n次*/printf("%d ",deletemax());return 0;
}


建堆及其堆排序(建立最大堆)&＃xff1a;
思想&＃xff1a;建立最大堆&＃xff0c;最大元素为h[1]&＃xff0c;从小到大排序&＃xff0c;最大的放在后面&＃xff0c;将h[1]和h[n]交换。
交换后&＃xff0c;h[n]就是数组中最大的元素。
h[1]向下调整保持堆的特性。
最大元素已经归位&＃xff0c;n–。
直至堆的大小变成1为止。

#include
#include
#include
using namespace std;
int h[101];
int n;/*堆的大小*/
void swap(int x,int y)
{int t;t&＃61;h[x];h[x]&＃61;h[y];h[y]&＃61;t;
}
void siftdown(int i)/*传入一个需要向下调整的结点编号i,这里传入1,即从堆的顶点向下调整*/
{int t,flag&＃61;0;/*flag用来标记是否需要继续向下调整*/while(i*2<&＃61;n&&flag&＃61;&＃61;0)/*当i结点有儿子(其实是至少有左儿子的情况下)并且有需要继续调整的时候,循环就执行*/{if(h[i]<h[i*2])/*首先判断它和左儿子的关系,并用t记录值较大的结点编号*/t&＃61;i*2;elset&＃61;i;if(i*2&＃43;1<&＃61;n)/*右儿子存在,再对右儿子进行讨论*/{if(h[t]<h[i*2&＃43;1])t&＃61;i*2&＃43;1;}if(t!&＃61;i)/*最小的结点不是自己,说明子结点中有比父结点更小的*/{swap(t,i);i&＃61;t;/*更新i为刚才与它交换的儿子结点的编号*/}elseflag&＃61;1;/*父结点已经比两个子结点都小,不需要再进行调整*/}
}
void creat()
{int i;for(int i&＃61;n/2; i>&＃61;1; i--) /*从最后一个非叶结点到第1个结点依次进行向上调整*/siftdown(i);
}
void heapsort()
{while(n>1){swap(1,n);n--;siftdown(1);}
}
int main()
{int i,num;scanf("%d",&num);for(int i&＃61;1; i<&＃61;num; i&＃43;&＃43;)scanf("%d",&h[i]);n&＃61;num;creat();/*建堆*/heapsort();for(int i&＃61;1; i<&＃61;num; i&＃43;&＃43;) /*删除顶部元素,连续删除n次*/printf("%d ",h[i]);return 0;
}