Heap sort using linked lists

Question

I was wondering if anyone has ever used linked lists to do heap sort and if they have could they provide the code. I have been able to do heapsort using arrays, but trying to do it in linked lists seems unpractical and just a pain in the you know where. I have to implement linked lists for a project Im doing, any help would be greatly appreciated.

Also I am using C.

Answer 1

The answer is "you don't want to implement heap sort on a linked list."

Heapsort is a good sorting algorithm because it's O(n log n) and it's in-place. However, when you have a linked list heapsort is no longer O(n log n) because it relies on random access to the array, which you do not have in a linked list. So you either lose your in-place attribute (by needing to define a tree-like structure is O(n) space). Or you will need to do without them, but remember that a linked list is O(n) for member lookup. Which brings the runtime complexity to something like O(n^2 log n) which is worse than bubblesort.

Just use mergesort instead. You already have the O(n) memory overhead 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 (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);
        }
}

//only heapify function