树：
树是指任意两点之间有且仅有一条路径的无向图(即 不包含回路的连通无向图)
树的特点：
1.任意两点有且仅有一条路径
2.如果一个树有n个节点，那么它一定恰好有n-1条边
3.在一个树中加一条边 一定会构成回路
根节点：没有父节点的节点
叶节点：没有子节点的节点
内部节点：既不是根节点也不是叶节点的节点（即 有父亲也有儿子）
二叉树：
二叉树是每一个节点最多只有两个儿子的特殊树左边为左儿子，右边为右儿子
满二叉树：
如果二叉树中每个内部节点都有两个儿子，这样的二叉树称为满二叉树。
它的特性：如果深度为h，则节点数一定为2^h-1;
完全二叉树：若设二叉树的深度为h,则除了第h层外，其余各层(1~h-1)的节点数都达到了最大个数。第h层，
从左到右连续缺少若干节点~
如果完全二叉树的一个节点有右儿子，那它一定有左儿子。
如果完全二叉树的一个父节点为k，那它的左儿子的编号为2k,右儿子为2k+1
如果已知儿子（左儿子或右儿子）的编号为x，那它的父节点的编号为x/2
最小堆：所有父节点都比子节点小（根节点最小）
最大堆：所有父节点都比子节点大（根节点最大）
#pragma mark - - 建堆（最小堆）
/*
方式一: 以空堆开始，每次向堆中插入一个元素，直到所有的元素插入完毕。（向上调整）时间复杂度O(NlogN)
方式二: 一维数组可以看作成一个完全二叉树~如果二叉树中每一个节点都满足最小（大）堆,则这个完全二叉树是最小（大）堆。
叶节点不用处理，所以只要所有非叶节点满足最小（大）堆，那这个完全二叉树是最小（大）堆~ 时间复杂度O(N)
最后一个非叶节点是n/2
*/
void swap(int x,int y,int h[]) {
int t;
t = h[x];
h[x] = h[y];
h[y] = t;
return ;
}
#pragma mark - 方式一
void siftupMin(int i,int h[]) {
if (i==1) {
return ;
}
int flag = 0; // 标示是否需要继续调整
while (i!=1 && flag==0) {
// 判断是否比父节点小
// 最小堆 父节点比子节点小
if (h[i]<h[i/2]) {
swap(i, i/2, h);
}else {
flag =1;
}
i=i/2; // 更新i的编号为父节点的编号 从而方便下一次继续向上调整
}
}
-(void)createMinHeap1{
int a[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int h[15];
for (int i=1; i<=14; i++) {
h[i] = a[i];
siftupMin(i, h);
}
// 打印最小堆
printf("\n");
for (int i=1; i<=14; i++) {
printf("%5d",h[i]);
}
printf("\n\n");
}
#pragma mark - 方式二
void siftdownMin(int i,int h[],int n) {
int flag=0; // 标示是否需要继续向下调整
int t=0; // 存储较小的编号
// 2*i<=n 判断是否有子节点
while (2*i<=n && flag==0) {
// 判断左子节点是否比父节点小
if (h[2*i]<h[i]) {
t = 2*i;
}else {
t = i;
}
// 判断是否有右子节点
if (2*i+1<=n) {
// 判断右子节点是否比当前最小的节点小
if (h[2*i+1]<h[t]) {
t=2*i+1;
}
}
// 判断i是否等于t
if (t!=i) {
// 交换
swap(i, t, h);
i = t; // 更新i为t，便于下一次的向下调整
}else {
flag =1;
}
}
}
-(void)createMinHeap2 {
int h[15]={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int n=14;
for (int i=n/2; i>=1; i--) {
siftdownMin(i, h, n);
}
// 打印最小堆
printf("\n");
for (int i=1; i<=14; i++) {
printf("%5d",h[i]);
}
printf("\n\n");
}
#pragma mark - - 建堆（最大堆）
#pragma mark - 方式一
void siftupMax (int i,int h[]) {
if (i==1) {
return ;
}
int flag =0 ; // 标示是否需要向上调整
while (i!=1 && flag==0) {
if (h[i]>h[i/2]) {
swap(i, i/2, h);
}else {
flag =1;
}
i= i/2; // 继续向上调整
}
}
-(void)createMaxHeap1 {
int a[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int h[15];
for (int i=1; i<=14; i++) {
h[i] = a[i];
siftupMax(i, h);
}
// 打印最大堆
printf("\n");
for (int i=1; i<=14; i++) {
printf("%5d",h[i]);
}
printf("\n\n");
}
#pragma mark - 方式二
void siftdownMax(int i,int h[],int n) {
int flag=0;
int t=0; // 记录较大值的编号
while (2*i<=n && flag==0) {
if (h[2*i] > h[i]) {
t=2*i;
}else {
t=i;
}
if (2*i+1<=n) {
if (h[2*i+1] > h[t]) {
t= 2*i+1;
}
}
if (t!=i) {
swap(i, t, h);
i=t;
}else {
flag =1;
}
}
}
-(void)createMaxHeap2 {
int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int n=14;
for (int i=n/2; i>=1; i--) {
siftdownMax(i, h, n);
}
// 打印最大堆
printf("\n");
for (int i=1; i<=14; i++) {
printf("%5d",h[i]);
}
printf("\n\n");
}
#pragma mark - - 堆排序(从小到大) O(NlogN)
// 删除顶部节点(最小堆)
// 删除顶部节点就是把最后一个节点的值赋值给顶部节点，同时n-1,并向下调整
int n;
int deleteRootMin(int h[]){
int t;
t=h[1];
h[1] = h[n];
n--;
siftdownMin(1, h, n);
return t;
}
-(void)heapsortMin {
// 建堆（最小堆）
int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int m=14;
n=14;
for (int i=m/2; i>=1; i--) {
siftdownMin(i, h, n);
}
printf("\n");
for (int i=1; i<=m; i++) {
printf("%5d",deleteRootMin(h));
}
printf("\n\n");
}
#pragma mark - - 堆排序(从大到小)
// 删除顶部节点(最大堆)
// 删除顶部节点就是把最后一个节点的值赋值给顶部节点，同时n-1,并向下调整
int deleteRootMax(int h[]){
int t;
t=h[1];
h[1] = h[n];
n--;
siftdownMax(1, h, n);
return t;
}
-(void)heapsortMax {
// 建堆（最大堆）
int h[15] ={0,99,2,5,12,7,17,25,19,36,1,22,28,46,92};
int m=14;
n=14;
for (int i=m/2; i>=1; i--) {
siftdownMax(i, h, n);
}
printf("\n");
for (int i=1; i<=m; i++) {
printf("%5d",deleteRootMax(h));
}
printf("\n\n");
}
