Кучи сортировка с использованием связанных списков
Мне было интересно, использовал ли кто-нибудь когда-либо связанные списки для сортировки кучи, и если да, то могут ли они предоставить код. Я смог сделать heapsort, используя массивы, но попытка сделать это в связанных списках кажется непрактичной и просто болью в вы знаете, где. Я должен реализовать связанные списки для проекта, который я делаю, любая помощь будет очень признательна.
Также я использую C.
3 ответа:
Ответ: "вы не хотите реализовывать сортировку кучи в связанном списке."
Heapsort-хороший алгоритм сортировки, потому что он
O(n log n)
и он на месте. Однако, когда у вас есть связанный список, heapsort больше неO(n log n)
, потому что он полагается на случайный доступ к массиву, которого у вас нет в связанном списке. Таким образом, вы либо теряете свой атрибут in-place (но необходимость определить древовидную структуру-это пространствоO(n)
). Или вам нужно будет обойтись без них, но помните, что связанный список являетсяO(n)
для поиска членов. Что приводит сложность выполнения к чему-то вродеO(n^2 log n)
, что хуже, чем bubblesort.Только вместо того, чтобы использовать сортировка слиянием. У вас уже есть требование к накладным расходам памяти
O(n)
.
//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 (i.e 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<stdio.h> #include<malloc.h> #include<stdlib.h> #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(¤t->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); } } } }
#include<stdio.h> #include<stdlib.h> 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 && lar<n) { temp=temp->next; lar--; } N *temp1=*head; lar=l; while(lar!=0 && lar<=n) { temp1=temp1->next; lar--; } if(l<n && temp->data<temp1->data) { larg=l; lar=l; temp=*head; while(lar!=0 && lar<n) { temp=temp->next; lar--; } } lar=r; temp1=*head; while(lar!=0 && lar<n) { temp1=temp1->next; lar--; } if(r<n && temp->data<temp1->data) { 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); } }
/ / только функция heapify