我想知道是否有人曾经使用链表进行堆排序，如果他们有，他们可以提供代码吗？我已经能够使用数组进行堆排序，但是尝试在链表中执行此操作似乎不切实际，并且只是您知道在哪里的痛苦。我必须为我正在做的项目实现链表，任何帮助将不胜感激。
我也在使用 C。
答案是"你不想在链表上实现堆排序"。
堆排序是一个很好的排序算法，因为它是O(n log n)的，而且是就地的。 但是，当您拥有链表时，堆排序不再O(n log n)，因为它依赖于对数组的随机访问，而链表中没有该数组。 因此，您要么丢失就地属性（因为需要定义树状结构是O(n)空间）。 或者你需要没有它们，但请记住，链表是成员查找O(n)。 这使得运行时的复杂性达到O(n^2 log n)比 bubblesort 更糟糕。
只需使用合并排序即可。 您已经满足了O(n)内存开销要求。
//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 numbern");
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 moren");
}
printf("Number of nodes added : %dn",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("nn");
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);
}
}
}
}
#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);
}
}
/仅堆函数