Heap-Sortierung mit verknüpften Listen

Question

Ich frage mich, ob jemand jemals verknüpfte Listen zu Heap-Sortierung verwendet hat und wenn sie haben, könnten sie den Code bereitstellen. Ich war in der Lage, Heapsort mit Arrays, aber versuchen, es in verknüpften Listen zu tun scheint unpraktisch und nur ein Schmerz in der Sie wissen, wo. Ich muss verkettete Listen für ein Projekt implementieren Im tun würde jede mögliche Hilfe sehr geschätzt werden.

Auch ich bin mit C.

Answer 1

Die Antwort lautet „Sie wollen nicht die Stapelsortier auf eine verknüpfte Liste implementieren.“

Heapsort ist ein guter Sortieralgorithmus, weil es O(n log n) ist und es in-Place ist. Wenn Sie jedoch eine verknüpfte Liste haben, ist heapsort nicht mehr O(n log n), da sie auf den Direktzugriff auf das Array angewiesen ist, das Sie nicht in einer verknüpften Liste haben. So verlieren Sie entweder Ihr In-Place-Attribut (aber müssen Sie eine baumartige Struktur definieren, ist O(n) Leerzeichen). Oder Sie müssen auf sie verzichten, aber denken Sie daran, dass eine verknüpfte Liste O(n) für die Mitgliedersuche ist. Das bringt die Laufzeitkomplexität zu etwas wie O(n^2 log n), was schlimmer ist als bubblesort.

Verwenden Sie stattdessen Mergesort. Sie haben bereits die Speicherbedarfsanforderung 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 (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(&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); 
     } 
} 

// nur heapify Funktion