我想知道是否有人曾经使用链表进行堆排序，如果他们可以提供代码。我已经能够使用数组进行堆排序，但尝试在链表中进行似乎不切实际，而且你知道在哪里会很痛苦。我必须为我正在做的项目实施链接列表，任何帮助将不胜感激。
我也在使用C。
问问题
30275 次
3 回答
23
答案是“你不想在链表上实现堆排序”。
Heapsort 是一个很好的排序算法，因为它是O(n log n)并且它是就地的。但是，当您拥有链表时，堆排序不再O(n log n)是因为它依赖于对数组的随机访问，而您在链表中没有。所以你要么失去你的就地属性（通过需要定义一个树状结构是O(n)空间）。或者您将需要不使用它们，但请记住链接列表O(n)用于成员查找。这将运行时复杂性带到了O(n^2 log n)比冒泡排序更糟糕的程度。
只需使用合并排序即可。您已经有O(n)内存开销要求。
于 2012-06-04T17:50:39.653 回答
0
//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(¤t->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);
}
}
}
}
于 2012-07-19T17:56:59.330 回答
-1
#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函数
于 2016-10-17T08:54:34.950 回答