Chinaunix首页 | 论坛 | 博客

mrkeywang的ChinaUnix博客

首页　| 　博文目录　| 　关于我

mrkeywang

  • 博客访问： 12938
  • 博文数量： 16
  • 博客积分： 0
  • 博客等级： 民兵
  • 技术积分： 170
  • 用 户 组： 普通用户
  • 注册时间： 2013-05-08 11:44
文章分类

全部博文（16）

文章存档

2014年（16）

我的朋友
最近访客
推荐博文
相关博文
区间堆

分类： C/C++

2014-09-10 17:31:55


点击(此处)折叠或打开



  3. /*数组中第一个元素存放数组的长度len和当前的元素个数index*/
  4. struct elem {
  5.         union {
  6.                 int left;
  7.                 int index;
  8.         };
  9.         union {
  10.                 int right;
  11.                 int len;
  12.         };
  13. };
  14. int getmin(struct elem *heap)
  15. {
  16.         if (heap->index == 0) {
  17.                 fprintf(stderr, "the heap is empty\n");
  18.                 return INT_MIN;
  19.         }

  21.         return heap[1].left;
  22. }
  23. int getmax(struct elem *heap)
  24. {
  25.         if (heap->index == 0) {
  26.                 fprintf(stderr, "the heap is empty\n");
  27.                 return INT_MAX;
  28.         }
  29.         if (heap->index == 1)
  30.                 return heap[1].left;
  31.         else
  32.                 return heap[1].right;
  33. }
  34. void insert(struct elem *elem, int key)
  35. {
  36.         if (elem->index == elem->len) {
  37.                 fprintf(stderr, "need increase the len\n");
  38.                 return;
  39.         }
  40.         elem->index ++;
  41.         int idx = (elem->index + 1) / 2;
  42.         int idy = (elem->index + 1) % 2;

  44.         if (idy == 0) {
  45.                 elem[idx].left = elem[idx].right = key;
  46.         } else if (elem[idx].left > key) {
  47.                 elem[idx].right = elem[idx].left;
  48.                 elem[idx].left = key;
  49.         } else {
  50.                 elem[idx].right = key;
  51.         }

  53.         int x = idx;
  54.         int z = x / 2;
  55.         int tkey = elem[x].left;
  56.         while (z > 0 && elem[z].left > tkey) {
  57.                 elem[x].left = elem[z].left;
  58.                 x = z;
  59.                 z = x / 2;
  60.         }
  61.         elem[x].left = tkey;

  63.         x = idx;
  64.         z = x / 2;
  65.         tkey = elem[x].right;
  66.         while (z > 0 && elem[z].right < tkey) {
  67.                 elem[x].right = elem[z].right;
  68.                 x = z;
  69.                 z = x / 2;
  70.         }
  71.         elem[x].right = tkey;

  73.         if (idy == 0 && elem[idx].left == key)
  74.                         elem[idx].left = elem[idx].right;
  75. }
  76. void delmin(struct elem *elem)
  77. {
  78.         if (elem->index == 0) {
  79.                 fprintf(stderr, "cant delete an empty heap\n");
  80.                 return;
  81.         }
  82.         if (elem->index == 1) {
  83.                 elem->index --;
  84.                 return;
  85.         }
  86.         int idx = (elem->index + 1) / 2;
  87.         int idy = (elem->index + 1) % 2;
  88.         elem[1].left = idy==0 ? elem[idx].left : elem[idx].right;
  89.         elem->index--;

  91.         int end = (elem->index + 1) / 2 / 2;
  92.         int i = 1;
  93.         while (i <= end) {
  94.                 int k = 2*i;
  95.                 if ((k+1)*2-1 <= elem->index && \
  96.                 elem[k].left > elem[k+1].left) {
  97.                         k ++;
  98.                 }
  99.                 if (elem[i].left > elem[k].left) {
  100.                         int tmp = elem[i].left;
  101.                         elem[i].left = elem[k].left;
  102.                         elem[k].left = tmp;
  103.                         i = k;
  104.                         if (2*k <= elem->index &&\
  105.                         elem[k].left > elem[k].right) {
  106.                                 tmp = elem[k].left;
  107.                                 elem[k].left = elem[k].right;
  108.                                 elem[k].right = tmp;
  109.                         }
  110.                 } else
  111.                         break;
  112.         }
  113. }
  114. void delmax(struct elem *elem)
  115. {
  116.         if (elem->index == 0) {
  117.                 fprintf(stderr, "cannot delete, an empty tree\n");
  118.                 return;
  119.         }
  120.         if (elem->index <= 2) {
  121.                 elem->index--;
  122.                 return;
  123.         }

  125.         int idx = (elem->index+1) / 2;
  126.         int idy = (elem->index+1) % 2;
  127.         elem[1].right = idy==0 ? elem[idx].left : elem[idx].right;
  128.         elem->index --;

  130.         int end = (elem->index + 1) / 2 / 2;
  131.         int i = 1;
  132.         while (i <= end) {
  133.                 int k = 2*i;
  134.                 if ((k+1)*2 <= elem->index &&\
  135.                 elem[k].right < elem[k+1].right) {
  136.                         k++;
  137.                 }

  139.                 if (elem[i].right < elem[k].right) {
  140.                         int tmp = elem[i].right;
  141.                         elem[i].right = elem[k].right;
  142.                         elem[k].right = tmp;

  144.                         if (elem[k].left > elem[k].right) {
  145.                                 tmp = elem[k].left;
  146.                                 elem[k].left = elem[k].right;
  147.                                 elem[k].right = tmp;
  148.                         }
  149.                         i = k;
  150.                  } else
  151.                         break;
  152.         }
  153. }

阅读(524) | 评论(0) | 转发(0) |
0

上一篇：二项树

下一篇：没有了

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6