堆排序

时间：2010-11-15 来源：xiayongchun

#include <stdio.h>
#define N 7
#define SWAP(a,b) {int tmp=a;a=b;b=tmp;}
int A[N]={1,2,3,4,5,6,7};
struct Node
{
int data;
Node* left;
Node* right;
};
Node* create(int n)
{
if(n<N)
{
  Node *cur=new Node;
  cur->data=A[n];
  cur->left=create(2*n+1);
  cur->right=create(2*n+2);
  return cur;
}
return NULL;
}
void sift(Node* cur)
{
while(cur->left)
{
  if(cur->data<cur->left->data
   &&(cur->right==NULL||cur->right->data<cur->left->data))
  {
   SWAP(cur->data,cur->left->data);
   cur=cur->left;
  }
  else if(cur->right!=NULL&&cur->data<cur->right->data
   &&cur->left->data<cur->right->data)
  {
   SWAP(cur->data,cur->right->data);
   cur=cur->right;
  }
  else
   return;
}
}
void buildheap(Node* root)
{
if(root)
{
  if(root->left)
   buildheap(root->left);
  if(root->right)
   buildheap(root->right);
  sift(root);
}
}
void print(Node* root)
{
if(root)
{
  printf("结点%d: ",root->data);
  if(root->left)
   printf("左孩子:%d ",root->left->data);
  if(root->right)
   printf("右孩子:%d ",root->right->data);
  putchar('\n');
  print(root->left);
  print(root->right);
}
}
int main()
{
Node* root=create(0);
buildheap(root);
print(root);
return 0;
} http://wenku.baidu.com/view/066b923231126edb6f1a1066.html