堆
1.堆
堆的逻辑结构是一颗完全二叉树
堆的物理结构是一个顺序表
通过下标去实现父子节点关系
leftchild=parent*2+1 rightchild=parent*2+2 parent=(child-1)/2;
就类似于下图
2.堆的两个特性
大堆：所有父亲大于等于孩子
小堆：所有父亲小于等于孩子
结构性：用数组表示的完全二叉树
有序性：任意结点的关键字是其子树所有结点的最大值（或最小值）
“最大堆”也称“大堆顶”：最大值
“最小堆”也称“小堆顶”：最小值
3 .向下调整算法（以大堆为例）
//向下调整算法(左右子树必须是大堆) void AdjustDown(int*a,int n,int root) { int parent=root; int child=parent*2+1; while(child<n) { if( child+1<n && a[child+1]>a[child]) { child+=1; } if(a[child]>a[parent]) { Swap(&a[child],&a[parent]); parent=child; child=parent*2+1; } else { break; } } }
那么左右子树不是小堆，就不能直接使用向下调整算法了，怎么办 可以倒着从最后一颗子树开始调 从最后一个非叶子结点开始调，最后一个非叶子节点的下标是（n-1-1)/2
for(i=(n-2)/2;i>=0;i--) { AdjustDown(arr,n,i); }
2.排序
如果我们要给数组排升续，那么我们需要建大堆
每一次向下调整都可以找出一个最大的数放在第一个位置，
我们可以把第一个和最后一个交换，然后把最后一个数（也就是找出的那个最大的数）不看作
前n-1个数，继续向下调整，选出次大的数，再跟倒数第二个位置交换，后面过程以此类推。
到最后就可以完成排序。
//建堆O（n） for(i=(n-2)/2;i>=0;i--) { AdjustDown(arr,n,i); } //排升序，建大堆 int end=n-1; while(end>0) { Swap(&arr[0],&arr[end]); AdjustDown(arr,end,0); end--; }
4.完整代码
//交换两个数函数的分装 void Swap(int*x,int*y) { int temp=*x; *x=*y; *y=temp; } //向下调整算法(左右子树必须是大堆) void AdjustDown(int*a,int n,int root) { int parent=root; int child=parent*2+1; while(child<n) { if( child+1<n && a[child+1]>a[child]) { child+=1; } if(a[child]>a[parent]) { Swap(&a[child],&a[parent]); parent=child; child=parent*2+1; } else { break; } } } #include<stdio.h> int main() { int i=0; int arr[]={10,9,8,7,6,5,4,3,2,1}; int n=sizeof(arr)/sizeof(arr[0]); //建堆O（n） for(i=(n-2)/2;i>=0;i--) { AdjustDown(arr,n,i); } //排升序，建大堆 int end=n-1; while(end>0) { Swap(&arr[0],&arr[end]); end--; AdjustDown(arr,end,0); } for(i=0;i<n;i++) { printf("%d ",arr[i]); } return 0; }
5.时间复杂度的计算
用n表示元素个数
向下调整算法 ，最多向下调整高度（二叉树高度）次。
h=log(n);
所以一次向下调整的时间复杂度是log(n)
建堆的时间复杂度
T(n)=1*（h-1）+ 2* (h-2)+ 4* (h-3)+…2^(h-2)
T(n)= -h+2^h-1
建堆的时间复杂度就约等于O(N)
整体的时间复杂度O(N*logN)
