Chinaunix首页 | 论坛 | 博客
  • 博客访问: 457912
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: C/C++

2011-06-26 23:27:32

堆类似于一颗完全二叉树,其中的每个节点都对应一个数值,它可用于堆排序,也可以作为数据结构成为优先级队列(Dijkstra算法就可以使用堆来进行描述),通常有两种性质的堆:

1.大顶堆:每个根节点的数值大于其孩子节点的数值

2.小顶堆:每个根结点的数值小于其孩子节点的数值

而常见的操作有:

1.heap_min(小顶堆,获取堆的最小元素),heap_max(大顶堆,获取堆的最大元素)

2.heap_length:获取堆的元素个数

3.heap_key:将堆中某个节点数值进行修改

4.heap_insert:向堆中插入某个节点

5.heap_extract:删除(大顶堆的)最大元素或(小顶堆的)最小元素.

下面开始进行部分程序分析:

这里采用的不是数组方式的堆结构,而采用了链表方式的堆结构,其中数据结构声明如下:

  1. //堆中的节点
  2. struct heap_node
  3. {
  4.     long value;
  5.     struct heap_node *left;//左孩子节点
  6.     struct heap_node *right;//右孩子节点
  7.     struct heap_node *parent;//父节点
  8. }
  9. //堆中的根节点
  10. struct heap_root
  11. {
  12.     struct heap_node *root;//根结点
  13.     unsigned int length;//元素个数
  14.     int flag:1;//堆的性质,大顶堆(1),小顶堆(0)
  15. }

堆中节点初始化

  1. #define heap_node_init(ptr,_value) ({\
  2.         (ptr)->left = NULL;\
  3.         (ptr)->right = NULL;\
  4.         (ptr)->parent = NULL;\
  5.         (ptr)->value = _value;})

堆中根节点初始化

  1. #define heap_root_init(ptr,_flag,_value) ({\
  2.         heap_node_init(&ptr->root,_value);\
  3.         ptr->length = 1;\
  4.         ptr->flag = _flag;\
  5.         })
  6. #define heap_root_init_max(root) ({\
  7.         heap_root_init(root,1);\
  8.         })
  9. #define heap_root_init_min(root) ({\
  10.         heap_root_init(root,0);\
  11.         })

由于根节点中存放的就是最大或最小元素,这样访问起来就方便多了

  1. static inline struct heap_node* heap_min(struct heap_root *root)
  2. {
  3.         if(!root->flag)
  4.            return &root->root;
  5.            return NULL;
  6. }

  7. static inline struct heap_node* heap_max(struct heap_root *root)
  8. {
  9.         if(root->flag)
  10.             return &root->root;
  11.             return NULL;
  12. }

获取堆元素长度

  1. static inline int heap_length(struct heap_root *root)
  2. {
  3. return root->length;
  4. }

查找第一个没有左孩子或右孩子的节点

  1. void _find_heap_node(struct heap_node **q,struct heap_root *root)
  2. {
  3.     int i,j;
  4.     struct heap_node *p = &root->root;
  5.     struct heap_node node[root->length];
  6.     
  7.     j=0;
  8.     i=0;
  9.     
  10.     node[i ].left = p;
  11.     
  12.     while(j<i)
  13.     {
  14.      p = node[j ].left;
  15.     
  16.      if(!p->left||!p->right)
  17.      {
  18.         *q = p;
  19.         return;
  20.      }
  21.     
  22.      node[i ].left = p->left;
  23.      node[i ].left = p->right;

  24.     }
  25. }

从父节点维护堆属性

  1. static void _adjust_parent(struct heap_root* root,struct heap_node *node)
  2. {
  3.     struct heap_node *p = node;
  4.     struct heap_node *q = p->parent;
  5.     
  6.     while(p&&q)
  7.     {
  8.     //max heap
  9.     if(root->flag&&q->value >= p->value) break;
  10.     
  11.     else //min heap
  12.         if(!root->flag&&q->value <= p->value) break;
  13.     else //adjust
  14.     {
  15.         
  16.         exchange(p,q);
  17.         p = q;
  18.         q = q->parent;
  19.      }
  20.     }
  21.     
  22. }

从子节点维护堆属性

  1. static void _adjust_child(struct heap_root *root,struct heap_node *node)
  2. {
  3.     struct heap_node *left = node->left;
  4.     struct heap_node *right = node->right;
  5.     struct heap_node *temp = node;
  6.     
  7.     //max heap property
  8.     if(root->flag) {
  9.     
  10.     if(left && left->value > temp->value) temp = left;
  11.     if(right && right->value > temp->value) temp = right;
  12.     
  13.     if(temp != node)
  14.     {
  15.      exchange(temp,node);
  16.     _adjust_child(root,temp);
  17.     }
  18.     
  19.     }
  20.     //min heap property
  21.     else
  22.     {
  23.      if(left && left->value < temp->value ) temp = left;
  24.      if(right && right->value < temp->value) temp = right;
  25.     
  26.      if(temp != node)
  27.      {
  28.      exchange(temp,node);
  29.      _adjust_child(root,temp);
  30.      }
  31.     }
  32. }

替换堆中的元素

  1. int heap_key(struct heap_root *root,struct heap_node *node,long key)
  2. {
  3.     if(root->flag&&key<node->value) return -1;
  4.     
  5.     if(!root->flag&&key>node->value) return -1;
  6.     
  7.     node->value = key;
  8.     _adjust_parent(root,node);
  9.     
  10.     return 0;
  11. }

向堆中插入元素

  1. int heap_insert(struct heap_root *root,struct heap_node *node)
  2. {
  3.     struct heap_node *p;
  4.         
  5.     //find the fisrt node which is empty on left node or right
  6.     _find_heap_node(&p,root);

  7.     
  8.     if(p->left&&p->right) {
  9.         return -1;
  10.     }

  11.     if(!p->left)
  12.         p->left = node;
  13.     else if(!p->right)
  14.         p->right = node;

  15.     node->parent = p;
  16.     root->length =1;
  17.     //无孩子节点,只能从父节点中维护堆属性
  18.     _adjust_parent(root,node);

  19.     return 0;        
  20. }

提取出最大或最小元素并维护堆的属性

  1. struct heap_node* heap_extract(struct heap_root* root)
  2. {
  3.     struct heap_node *p,*q;
  4.     
  5.     p = NULL;
  6.     q = NULL;

  7.     if(root->length == 1)
  8.     {
  9.      root->length = 0;
  10.      return &root->root;
  11.     }

  12.     _last_heap_node(&p,root);

  13.     exchange(p,&root->root);
  14.     
  15.     q = p->parent;
  16.         
  17.     if(q->left == p)
  18.      q->left = NULL;
  19.     else
  20.      q->right = NULL;

  21.     root->length -= 1;
  22.     //根节点,只能从孩子中维护其属性
  23.     _adjust_child(root,&root->root);
  24.     return p;
  25.     
  26. } heap.rar   

阅读(1736) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~