Sort heaps using linked lists

Question

I was wondering if anyone ever used linked lists to sort heaps, and if they could provide code. I knew how to make arrays using arrays, but trying to do this in linked lists seems impractical, and just the pain is that you know where. I need to implement linked lists for the Im project, any help would be greatly appreciated.

I also use C.

Answer 1

The answer is: "You do not want to implement heap sorting in a linked list."

Heapsort is a good sorting algorithm because it is O(n log n) and it is in place. However, with a linked list, heapsort is no longer O(n log n) , since it relies on random access to an array that you do not have in the linked list. Thus, you either lose your attribute in place ( O(n) space is required to define a tree structure). Or you may have to do without them, but remember that the linked list is for finding O(n) members. Which makes it difficult to run into something like O(n^2 log n) , which is worse than bubble sorting.

Just use mergesort instead. You already have an O(n) memory requirement.

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<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(&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<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); } } 

// only heapify function