堆的实现，堆排序，咕咕咕

1.堆的实现

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int hp;typedef struct heap
{hp* data;int size;int capacity;
}heap;
//堆的初始化
void heapinit(heap* p)
{
p->data=NULL;
p->size=0;
p->capacity=0;
}
//创建堆
heap* createheap()
{heap* newheap=(heap*)malloc(sizeof(heap));if(newheap==NULL){perror("newheap malloc");exit(1);}heapinit(newheap);return newheap;
}
//堆的销毁
void destroyheap(heap* p)
{if(p==NULL) return;free(p->data);free(p);
}
//交换
void swap(hp* a,hp* b)
{hp temp=*a;*a=*b;*b=temp;
}
//向上调整堆
void siftup(heap* h,int x)
{
while(x>0)
{int parent=(x-1)/2;if(h->data[parent]<=h->data[x]) break;swap(&h->data[parent],&h->data[x]);x=parent;
}
}
//堆的插入
void heappush(heap* p,hp x)
{if(p->size==p->capacity){int newcapacity=p->capacity==0?4:p->capacity*2;hp* newdata=(hp*)realloc(p->data,newcapacity*sizeof(hp));if(newdata==NULL){perror("newdata realloc");exit(1);}p->data=newdata;p->capacity=newcapacity;}p->data[p->size]=x;p->size++;siftup(p,p->size-1);
}
//向下调整堆
void siftdown(heap* p,hp x)
{int left=2*x+1;int right=2*x+2;int largest=x;if(left<p->size&&p->data[left]>p->data[largest])largest=left;if(right<p->size&&p->data[right]>p->data[largest])largest=right;if(largest!=x){swap(&p->data[largest],&p->data[x]);siftdown(p,largest);}
}
//删除顶堆
void heapdelete(heap* h)
{if(h->size==0) return;h->data[0]=h->data[h->size-1];h->size--;siftdown(h,0);
}
//获取堆顶元素
hp heapmax(heap* p)
{assert(p->size>0);return p->data[0];
}
//判断是否为空
int heapempty(heap* p)
{
return p->size==0;
}
//获取堆的大小
int heapsize(heap* p)
{return p->size;
}

2.堆排序

//调整堆，使其满足最大堆性质
void heapify(vector<int>& arr,int n,int i)
{int largest=i;int left=2*n+1;int right=2*n+2;if(left<n&&arr[left]>arr[largest]) largest=left;if(right<n&&arr[right]>arr[largest]) largest=right;if(largest!=i){swap(arr[i],arr[largest]);heapify(arr,n,largest);}
}
//堆排序函数
void heapsort(vector<int>& arr)
{int n=arr.size();for(int i=n/2-1;i>=0;i++){heapify(arr,n,i);}for(int i=n-1;i>0;i--){swap(arr[0],arr[i]);heapify(arr,n,i);}
}

3.树

树是一种非线性的数据结构，由n个有限结点组成。有一个特殊的结点，称为根结点，根结点没有前驱结点。

除根结点外，其余结点被分成M个互不相交的集合，T1,T2.......Tm,其中每一个集合又是一棵结构与树类似的子树，每个子树的根结点有且只有一个前驱点，可以有0个或多个后续，树是递归定义的。

树有父节点，子节点(相对的）。

结点的度：一个结点有几个孩子，就有多少度。

树的度：最大结点的度。

叶子结点：度为0的结点

分支结点：度不为0的结点。

兄弟结点：具有相同父结点的结点。

结点的层次：根为第1层，每一层递推。

树的高度：树中结点的最大层次。

结点的祖先：从根到该结点所经分支上的所有结点。

结点的子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

森林：由m棵互不相交的树的集合。

树的孩子兄弟表示
struct TreeNode
{
struct Node* child;左边开始的第一个孩子结点
struct Node* brother;指向其右边的下一个兄弟结点
int data;
};

文件系统利用树形结构来组织管理文件和文件夹。

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

二叉树特点：不存在度大于2的结点。子树有左右之分，是有序树。

满二叉树：若是层数为k,结点为2^k-1

（根结点层数为1，非空二叉树上i层最多2^i-1个结点）
（根结点层数为1，深度为h的二叉树的最大结点数为2^h-1）

{根结点层数为1，有n个结点的满二叉树深度h=log2（n+1）

完全二叉树：最后一层可以不满足每个结点有2个子节点，但要满足从左向右填充。其余层必须都满足满结点。

二叉树可以有顺序结构和链式结构2种

（顺序结构的实现请看上面堆的实现）！！！！！！！！！！！！！！！！！！！！！！！！！！

有n个结点的完全二叉树，每个结点标记序号，对于序号为i的结点：

若i>0,i的父结点序号：(i-1)/2,i=0则没有父结点

若2*i+1<n,左孩子序号2*i+1,否则没有。

若2*i+2<n,右孩子序号2*i+2，否则没有。

向上调整算法，先把元素插入堆的末尾，如果破坏了堆的性质，把插入的结点顺着父结点向上调整位置，时间复杂度O(nlog n).

向下调整算法，把堆顶的元素与最后一个元素互换，删除堆最后一个元素，把堆顶元素向下调整至满足堆特性，时间复杂度O(n).

具体实现看上面堆实现的代码