1.找TopK问题

要找到最前面的k个元素

void swap(int *a,int *b)
{int temp=*a;*a=*b;*b=temp;
}
//向下调整最小堆
void minheapify(int arr[],int n,int index)
{int left=2*index+1;int right=2*index+2;int smallest=index;if(left<n&&arr[left]<arr[smallest]) smallest=left;if(right<n&&arr[right]<arr[smallest]) smallest=right;if(smallest!=index){swap(&arr[smallest],&arr[index]);minheapify(arr,n,smallest);}
}
//创建最小堆
void buildminheap(int arr[],int n)
{for(int i=(n-2)/2;i>=0;i--){minheapify(arr,n,i);}
}
//寻找顶端
void findtopk(int arr[],int n,int k)
{if(k<=0||k>n){return;}int* heap=(int*)malloc(k*sizeof(int));for(int i=0;i<k;i++){heap[i]=arr[i];}buildheap(arr,k);for(int i=k;i<n;i++){if(arr[i]>heap[0]){heap[0]=arr[i];minheapify(heap,k,0);}for(int i=0;i<k;i++){printf("%d\n",heap[i]);}free(heap);
}

时间复杂度O(n)=k+(n-k)log2 k

2.链式二叉树

typedef int BT
typedef struct BTNode
{
struct BTNode* left;//左孩子
struct BTNdde* right;//右孩子
BT val;
}BTNode;BTNode* BuyBTNode(int val)
{
BTNode* newnode=(BTNode*)malloc(sizeof(BTNode));
if(newnode==NULL)
{
perror("malloc");
return NULL;
}
newnode->val=val;
newnode->left=NULL;
newnode->right=NULL;
return newnode;
}
BTNode* CreateTree()
{
BTNode* n1=BuyBTNode(1);
BTNode* n2=BuyBTNode(2);
BTNode* n3=BuyBTNode(3);
BTNode* n4=BuyBTNode(4);
BTNode* n5=BuyBTNode(5);
BTNode* n6=BuyBTNode(6);
BTNode* n7=BuyBTNode(7);
n1->left=n2;
n1->right=n4;
n2->left=n3;
n4->left=n5;
n4->right=n6;
n5->left=n7;
return n1;
}

前序遍历：访问顺序：根结点，左子树，右子树

中序遍历：访问顺序：左子树，根结点，右子树

后序遍历：访问顺序：左子树，右子树，根结点

void PreOrder(BTNode* root)
{
if(root==NULL)
{
printf("N");
return;
}
printf("%d",root->val);
PreOrder(root->left);
PreOrder(root->right);
}void InOrder(BTNode* root)
{
if(root==NULL)
{
printf("N");
return;
}
InOrder(root->left);
printf("%d",root->val);
InOrder(root->right);
}void PostOrder(BTNode* root)
{
if(root==NULL)
{
printf("N");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d",root->val);
}