堆使用链接列表排序

我想知道是否有人曾使用链表进行堆排序，如果有人可以提供代码。 我已经能够使用数组进行堆栈操作，但是尝试在链接列表中进行操作似乎是不切实际的，只是你知道在哪里痛苦。 我必须为我正在做的项目实现链接列表，任何帮助将不胜感激。

我也在使用C.

Answer 1

答案是“你不想在链表上实现堆排序。”

Heapsort是一个很好的排序算法，因为它是O(n log n)并且它是就地的。 但是，当您有链接列表时，heapsort不再是O(n log n)因为它依赖于对数组的随机访问，而链接列表中没有该数组。 因此，要么丢失了就地属性（但需要定义树状结构是O(n)空间）。 或者您将需要不使用它们，但请记住链接列表是O(n)用于成员查找。 这使运行时复杂性变得像O(n^2 log n) ，这比bubblesort更糟糕。

只需使用mergesort。 您已经有O(n)内存开销要求。

Answer 2

 //Heap Sort using Linked List //This is the raw one //This getRoot function will replace the root with number in the last node, after the main prints the largest number in the heap //The heapSort function will reconstruct the heap //addNode function is as same as in binary search tree //Note addNode and heapSort are recursive functions //You may wonder about the for loop used in main, this actually tells the depth of the tree (ie log base2 N) //With this value these functions find where to trverse whether left or right(direction), with help of macro GETBIT (0-left,1-right) #include #include #include #define GETBIT(num,pos) (num >> pos & 1) struct node { int data; struct node *left; struct node *right; }; typedef struct node node; int nodes; node *first, *tmp, *current; void addNode(node *,node *,int); void swap(int *, int *); void getRoot(node *, int); void heapSort(node *); int main() { int num; int cont,i,j; while(1) //It gets number from user if previous value is non zero number { printf("Enter a number\n"); scanf("%d",&num); if(!num) //i'm using 0 as terminating condition to stop adding nodes break; //edit this as you wish current = (node *)malloc(sizeof(node)); if(current == 0) return 0; current->data = num; nodes++; for(i=nodes,j=-1; i; i >>= 1,j++); if(first == 0) { first = current; first->left = 0; first->right = 0; } else addNode(first,first,j-1); printf("Need to add more\n"); } printf("Number of nodes added : %d\n",nodes); while(nodes) { printf(" %d -> ",first->data); //prints the largest number in the heap for(i=nodes,j=-1; i; i >>= 1,j++); //Updating the height of the tree getRoot(first,j-1); nodes--; heapSort(first); } printf("\n\n"); return 0; } void swap(int *a,int *b) { *a = *a + *b; *b = *a - *b; *a = *a - *b; } void addNode(node *tmp1,node *parent, int pos) { int dirxn = GETBIT(nodes,pos); // 0 - go left, 1 - go right if(!pos) { if(dirxn) tmp1->right = current; else tmp1->left = current; current->left = 0; current->right = 0; if(current->data > tmp1->data) swap(&current->data, &tmp1->data); } else if(dirxn) addNode(tmp1->right,tmp1,pos-1); else addNode(tmp1->left,tmp1,pos-1); if(tmp1->data > parent->data) swap(&parent->data,&tmp1->data); } void getRoot(node *tmp,int pos) { int dirxn; if(nodes == 1) return ; while(pos) { dirxn = GETBIT(nodes,pos); if(dirxn) tmp = tmp->right; else tmp = tmp->left; pos--; } dirxn = GETBIT(nodes,pos); if(dirxn) { first->data = tmp->right->data; free(tmp->right); tmp->right = 0; } else { first->data = tmp->left->data; free(tmp->left); tmp->left = 0; } } void heapSort(node *tmp) { if(!tmp->right && !tmp->left) return; if(!tmp->right) { if(tmp->left->data > tmp->data) swap(&tmp->left->data, &tmp->data); } else { if(tmp->right->data > tmp->left->data) { if(tmp->right->data > tmp->data) { swap(&tmp->right->data, &tmp->data); heapSort(tmp->right); } } else { if(tmp->left->data > tmp->data) { swap(&tmp->left->data, &tmp->data); heapSort(tmp->left); } } } } 

Answer 3

  #include #include typedef struct node { int data; struct node *next; }N; void maxheap(N **,int n,int i); void display(N **head) { N *temp1=*head; while(temp1!=NULL) { printf("%d ",temp1->data); temp1=temp1->next; } } int main(int argc,char *argv[]) { N *head=NULL,*temp,*temp1; int a,l,r,n,i; n=0; FILE *fp; fp=fopen(argv[1],"r"); while((a=fscanf(fp,"%d",&l))!=EOF) { temp=(N*)malloc(sizeof(N)); temp->data=l; temp->next=NULL; if(head==NULL) head=temp; else { temp1=head; while(temp1->next!=NULL) temp1=temp1->next; temp1->next=temp; } n++; } display(&head); printf("\nAfter heapifying..\n"); for(i=(n/2)-1;i>=0;i--) maxheap(&head,n,i); temp1=head; while(temp1!=NULL) { printf("%d ",temp1->data); temp1=temp1->next; } printf("\n"); } void maxheap(N **head,int n,int i) { int larg,l,r,tem,lar; larg=i; l=(2*i)+1; r=(2*i)+2; lar=larg; N *temp=*head; while(lar!=0 && larnext; lar--; } N *temp1=*head; lar=l; while(lar!=0 && lar<=n) { temp1=temp1->next; lar--; } if(ldatadata) { larg=l; lar=l; temp=*head; while(lar!=0 && larnext; lar--; } } lar=r; temp1=*head; while(lar!=0 && larnext; lar--; } if(rdatadata) { larg=r; lar=r; temp=*head; while(lar!=0 && lar<=n) { temp=temp->next; lar--; } if(larg!=i) { tem=temp->data; temp->data=temp1->data; temp1->data=tem; maxheap(&(*head),n,larg); } } 

//只有堆化function