递归方程求解
常系数线性同质递归方程
常系数线性同质递归方程.png
非同质递归方程
非同质递归方程1.png
非同质递归方程2.png
非同质递归方程2.png
Master Theorem
Master Theorem.png
堆
有n个节点的堆T，可以用一个数组H[1...n]表示。
- 根节点存储在H[1]
- T的节点x存在H[j]中，左右孩子节点在H[2j]和H[2j+1]
- H[j]的父节点如果不是根节点，则存储在H[j/2]中
堆.png
堆的基本操作
DELETE.png
INSERT.png
删除和插入时间负载度均为O(
SIFT-DOWN.png
SIFT-UP.png
#include<iostream>
using namespace std;
const n 1000;
int SIFT_UP(int h[n],int i)
{
bool done=false;
if(i==1) return 0;
while(i==1||done)
{
if(h[i]>h[i/2])
{
int temp=h[i];
h[i]=h[i+1];
h[i+1]=temp;
}
else{
i/=2;
done=true;
}
}
return 0;
}
int SIFT_DOWN(int h[n],int i)
{
bool done=false;
if(2*i>strlen(h)) return 0;
while(2*i>strlen(h)||done)
{
i=2*i;
if(i+1<=n&&h[i+1]>h[i]) i+=1;
if(h[i/2]<h[i])
{
int temp=h[i];
h[i]=h[i/2];
h[i/2]=h[i];
}
else done=true;
}
return 0;
}
int DELETE(int h[n],int i)
{
int x=h[i],y=h[n];
n-=n;
if(i=n+1) return 0;
h[i]=y;
if(y>x) SIFT_UP(h,i);
else SIFT_DOWN(h,i);
}
int DELETEMAX(int h[n])
{
int x=h[1];
DELETE(h,1);
return x;
}
void MAKEHEAP(int a[n])
{
for(int i=n/2;i>=1;i--) SIFT_DOWN(a,i);
}
void HEAPSORT(int a[n])
{
MAKEHEAP(a);
for(int j=n;j>=2;j--)
{
int temp=a[1];
a[1]=a[j];
a[j]=a[1];
}
SIFT_DOWN(a,1);
}
