一:二叉堆以及相关操作
二:例题
二叉堆是一个逻辑结构像堆的一个数据结构
对于这个堆,采用一维数组的存储方式,因为二叉堆是一颗完全二叉树,在一维数组的存储中可以这样表示,任何一节点下标 i,左子结点下标为 2*i , 右子结点下标为 2*i+1,其性质满足一节点的值大于(或小于,大于就是最大堆,小于就是最小堆)子树的每一个节点的值,但是对于子节点2*i 和 2*i+1之间的大小并没有关系,二叉堆有如下操作:
都用大根堆做例子,即:a[i] > a[i*2] && a[i] > a[i*2+1],小根堆只有点点不同
1.调整:将一个顶点作为根,(之前此根的子树满足大根堆性质)去调整这个点(只是子树满足,但次根的值不满足,所以才要调整根)
以下代码把长度为 n 的数组中 下标为 m 的点作为根,调整
void heap(int a[],int n,int m)//这里小根堆只要把 下面的 a[m] < a[m+1] 和 a[m] > a[m/2] 两处的大小符号取反 { int t; while(m*2 <= n)//条件是不越界 { m *= 2; // m 指到左子节点 if(m+1 <= n && a[m] < a[m+1]) m ++; //挑选左右子节点中较大的,如果右边大,m++就指向右子结点的位置, if(a[m] > a[m/2]) //如果左右子节点中选出来的那个点 大于根,那么就交换值,并且从挑选的位置再接着向下调整 { t = a[m]; a[m] = a[m/2]; a[m/2] = t; } else break; //如果挑选出来的不大于根,由于原子树满足大根堆性质,就没必要再调整 } }
2.建堆:结合上面,就有一个函数可以使一个无序的数组满足大根堆性质,
对于一个无序数组,其逻辑结构就是一个完全二叉树,一个堆的形式,那么对于有n个值的堆,(也就是一个长为n的一维数组),最底层我们可以从 n/2 开始,递减将每个位置都heap 一次,一层一层向上调整,那么调整完之后就是一个满足最大堆的性质的堆啦 (很多题目就要用到对一个数组建堆再处理)
void make_heap(int a[], int n) { for(int i = n/2; i > 0; i --) heap(a,n,i); }
3.堆排序:那么对于以上两个算法,结合,还可以得到一个堆排序的算法,就是对于一个无序的数组,排成有序数组(但是注意一个二叉堆不一定是有序,只是满足堆的性质)
引用:
用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录a[1](即堆顶)和无序区的最后一个记录a[n]交换,由此得到新的无序区a[1..n-1]和有序区a[n],且满足a[1..n-1]≤a[n]
③由于交换后新的根a[1]可能违反堆性质,故应将当前无序区a1..n-1]调整为堆。然后再次将a[1..n-1]中关键字最大的记录a[1]和该区间的最后一个记录a[n-1]交换,由此得到新的无序区a[1..n-2]和有序区a[n-1..n],且仍满足关系a[1..n-2]≤a[n-1..n],同样要将a[1..n-2]调整为堆。
……
直到无序区只有一个元素为止。
void heap_sort(int a[], int n) { make_heap(a,n); //建大根堆 for(int i = n; i > 1; i --)//建堆之后,a[1]为最大值,我们把它放到最后a[n]的位置, //那么后面只要将长度为n-1,位置为1的地方再调整一次就可以啦, //循环下来,每次挑选数组中最大的值放到后面不动它,调整前面,再找前面一节中最大的 //如此反复即可 { int t = a[1]; a[1] = a[i]; a[i] = t; heap(a,i-1,1); } }
4.那对对于一个堆,我们有的时候需要往里面添加一个数,那么对于这个添加的数,我们就有一个插入操作,(这里还是以大根堆为例),对于往堆中插入一个数,我们在插入的过程中就可以把它放到一个相对大小合适的位置,O(logN)的时间
void push_heap(int a[],int x)//在大小为n的堆尾部(也就是一维数组的n+1的位置) 添加 x
{
a[++n] = x; //添加
int i = n;
while(i > 1 && a[i/2] < x)//我们一层一层的往上比较,插入,对于一个大根堆,如果上面的数小,就要把小的数下降
{
a[i] = a[i/2];
i /= 2;
}
a[i] = x;//最后的插入
}
5.对应插入,就有删除,一般,对于一个大根堆,我们是每次需要用到一个数组的最大值才会建造一个大根堆,那么,有的时候选择最大的之后就要删除,那么为了方便下一次对于剩下的数中选择最大的,就要相应的操作
void pop_heap(int a[], int n) { int x = a[1]; a[1] = a[n]; n--; heap(a,n,1); return x; }
解题代码也放这里就太长啦,以后有机会还要更新,