堆中的路径
堆中的路径
0x00 问题描述
0x01 解题思路
这个题目不难,只需要先根据节点构造堆,然后再输出指定位置的节点到根的路径,位置不断除2即可实现
0x02 show me the code
#include <stdio.h>
#include <stdlib.h>
#define maxsize 1000
#define minnum -1000
typedef struct heap* minheap;
struct heap{
int* data;
int capacity;
int size;
};
void traversal(minheap h){
int i;
for(i=1;i<h->size+1;i++){
printf("(%d) ",h->data[i]);
}
printf("\n");
}
void adjust(minheap h,int parent){
int child=2*parent;
for(;child<=h->size;){
int minpos=child; //假设左儿子最小
if(child+1<=h->size&&h->data[child+1]<h->data[child]){
minpos=child+1;
}
if(h->data[parent]>h->data[minpos]){
int temp=h->data[parent];
h->data[parent]=h->data[minpos];
h->data[minpos]=temp;
parent=minpos;
child=2*parent;
}
else{
break;
}
}
}
minheap create_by_list(int* data,int size){
int i;
if(size>maxsize){
printf("超过最大容量!");
return NULL;
}
minheap h=(minheap)malloc(sizeof(struct heap));
h->capacity=maxsize;
h->data=(int*)malloc(sizeof(int)*(h->capacity+1));
h->size=0;
h->data[0]=-1000;
for(i=1;i<size+1;i++){
h->data[++h->size]=data[i-1];
}
int parent=h->size/2;
for(i=parent;i>0;i--){
adjust(h,i);
}
return h;
}
void getline(minheap h,int pos){
if(pos<=h->size&&pos>0){
printf("(%d)",h->data[pos]);
while(pos/=2){
printf("(%d)",h->data[pos]);
}
printf("\n");
}else{
printf("没有这个节点!");
}
}
int main(void){
int m,n;
int i;
scanf("%d %d",&m,&n);
int* a=(int*)malloc(sizeof(int)*m);
for(i=0;i<m;i++){
scanf("%d",a+i);
}
minheap h=create_by_list(a,m);
for(i=0;i<n;i++){
int pos=0;
scanf("%d",&pos);
getline(h,pos);
}
return 0;
}