リンクリストを使用したヒープソート

Question

誰かがヒープソートを行うためにリンクリストを使用していたかどうか、もし彼らがコードを提供できるのであれば疑問に思っていました。私は配列を使ってheapsortを行うことができましたが、リンクされたリストでそれをしようとするのは実用的ではないように思えます。私はプロジェクトのためにリンクされたリストを実装しなければならない、どんな助けも大いに感謝されるだろう。また

私は答えがC.

Answer 1

を使用しています「あなたは、リンクされたリストに、ヒープ・ソートを実装する必要はありません。」

HeapsortはO(n log n)であり、インプレースであるため、優れたソートアルゴリズムです。しかし、リンクされたリストを持っている場合、ヒープソートはO(n log n)でなくなります。これは、リンクされたリストにない配列へのランダムアクセスに依存するためです。だからあなたのインプレース属性を失う（しかし、木のような構造を定義する必要がありますO(n)スペースです）。または、メンバーシップなしで行う必要がありますが、メンバーリストのリンクリストはO(n)です。実行時の複雑さは、bubbles3よりも悪いO(n^2 log n)のようなものになります。

代わりに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 (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); 
     } 
} 

//のみheapify機能