首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >使用链表的堆排序

问使用链表的堆排序
EN

Stack Overflow用户
提问于 2012-06-05 01:27:12
回答 3查看 29.2K关注 0票数 6

我想知道是否有人使用链表进行堆排序,如果他们能提供代码。我已经能够使用数组进行堆排序,但尝试在链表中进行堆排序似乎不切实际,而且在你知道的地方也是一件痛苦的事情。我必须为我正在做的一个项目实施链表,任何帮助都会非常感谢。

我也在使用C语言。

EN

回答 3

Stack Overflow用户

回答已采纳

发布于 2012-06-05 01:50:40

答案是“你不想在链表上实现堆排序”。

堆排序是一个很好的排序算法,因为它是O(n log n)的,而且是就地排序的。但是,当您有一个链表时,heapsort不再是O(n log n),因为它依赖于对数组的随机访问,而这在链表中是没有的。所以你要么失去你的就地属性(因为需要定义一个树状结构就是O(n)空间)。或者,您将需要不使用它们,但请记住,对于成员查找,链表是O(n)。这带来了运行时的复杂性,比如O(n^2 log n),它比冒泡排序更糟糕。

只需使用mergesort即可。您已经有了O(n)内存开销要求。

票数 22
EN

Stack Overflow用户

发布于 2012-07-20 01:56:59

代码语言:javascript
复制
//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);
            }
        }
    }
}
票数 0
EN

Stack Overflow用户

发布于 2016-10-17 16:54:35

代码语言:javascript
复制
    #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函数

票数 -1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/10885449

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档