Chinaunix首页 | 论坛 | 博客
  • 博客访问: 664373
  • 博文数量: 141
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1114
  • 用 户 组: 普通用户
  • 注册时间: 2014-03-17 14:32
个人简介

小公司研发总监,即当司令也当兵!

文章分类

全部博文(141)

分类: LINUX

2016-02-16 22:15:00

二叉堆的定义

二叉堆是完全二叉树或者是近似完全二叉树。

二叉堆满足二个特性:

1.父结点的键值总是大于或等于(小于或等于)任何一个子节点的键值。

2.每个结点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆。下图展示一个最小堆:

由于其它几种堆(二项式堆,斐波纳契堆等)用的较少,一般将二叉堆就简称为堆。

堆的操作一般包括初始化、插入和删除:

下面是堆的简单实现:

点击(此处)折叠或打开

  1. typedef struct struct_heap {

  2.     int size;
  3.     int head;
  4.     int *data;
  5. }heap_t;

  6. void initHeap(heap_t **heap, int size)
  7. {
  8.     heap_t *pHeap;
  9.     
  10.     pHeap = (heap_t*)malloc(sizeof(*pHeap) + size * sizeof(int));
  11.     if (NULL == pHeap)
  12.     {
  13.         printf("malloc fail\n");
  14.         return;
  15.     }
  16.     memset(pHeap, 0, sizeof(*pHeap) + size * sizeof(int));

  17.     pHeap->size = size;
  18.     pHeap->head = 0;
  19.     pHeap->data = (int *) ((char *)pHeap + sizeof(*pHeap));

  20.     *heap = pHeap;
  21. }

  22. void insertHeap(heap_t *pHeap, int key)
  23. {
  24.     int cursor;
  25.     int tmp;

  26.     if (NULL == pHeap)
  27.         return;

  28.     if (pHeap->head == pHeap->size)
  29.     {
  30.         printf("Heap is full\n");
  31.         return;
  32.     }

  33.     pHeap->data[pHeap->head++] = key;

  34.     cursor = pHeap->head - 1;

  35.     while (cursor > 0)
  36.     {
  37.         if (pHeap->data[cursor] < pHeap->data[(cursor - 1)/2])
  38.         {
  39.             tmp = pHeap->data[cursor];
  40.             pHeap->data[cursor] = pHeap->data[(cursor-1) /2];
  41.             pHeap->data[(cursor-1) / 2] = tmp;
  42.             cursor = (cursor - 1) / 2;
  43.         }
  44.         else
  45.             break;
  46.     }
  47. }

  48. void deleteHeap(heap_t *pHeap, int *out)
  49. {
  50.     int cursor;
  51.     int temp;
  52.     int left;
  53.     int right;
  54.     int key;

  55.     if (NULL == pHeap)
  56.         return;

  57.     if (pHeap->head == 0)
  58.     {
  59.         printf("Heap is empty\n");
  60.         return;
  61.     }

  62.     *out = pHeap->data[0];
  63.     pHeap->data[0] = pHeap->data[pHeap->head - 1];
  64.     pHeap->head--;

  65.     cursor = 0;
  66.     while (cursor < pHeap->head -1)
  67.     {
  68.         key = pHeap->data[cursor];
  69.         left = key < 0 ? (key * -2) : (key * 2 + 1);
  70.         right = left + 1;

  71.         if ( (2 * cursor +1) <= pHeap->head -1)
  72.         {
  73.             left = pHeap->data[2*cursor +1];
  74.         }
  75.         if ( (2 * cursor +2) <= pHeap->head -1)
  76.         {
  77.             right = pHeap->data[2*cursor +2];
  78.         }

  79.         if (key > left && left < right)
  80.         {
  81.             temp = pHeap->data[cursor];
  82.             pHeap->data[cursor] = pHeap->data[2 * cursor + 1];
  83.             pHeap->data[2 * cursor + 1] = temp;
  84.             cursor = 2 * cursor + 1;
  85.         }
  86.         else if (key > right && right < left)
  87.         {
  88.             temp = pHeap->data[cursor];
  89.             pHeap->data[cursor] = pHeap->data[2 * cursor + 2];
  90.             pHeap->data[2 * cursor + 2] = temp;
  91.             cursor = 2 * cursor + 2;
  92.         }
  93.         else
  94.             break;
  95.     }
  96. }


堆排序
理解堆的插入和删除后,堆排序实现就非常简单了。下面是堆排序的简单实现:

点击(此处)折叠或打开

  1. // 在index位置插入新元素后,修正堆序列使之满足堆要求
  2. static void minHeapFixup(int list[], int index)
  3. {
  4.     int cursor;
  5.     int temp;

  6.     cursor = index;
  7.     while (cursor > 0)
  8.     {
  9.         if (list[cursor] < list[(cursor -1)/2])
  10.         {
  11.             temp = list[cursor];
  12.             list[cursor] = list[(cursor-1)/2];
  13.             list[(cursor-1)/2] = temp;
  14.             cursor = (cursor - 1) / 2;
  15.         }
  16.         else
  17.             break;
  18.     }
  19. }

  20. // 删除堆顶元素后,将最后一个元素移至堆顶,修正堆序列使之满足堆要求
  21. static void minHeapFixdown(int list[], int len)
  22. {
  23.     int cursor;
  24.     int temp;

  25.     int key;
  26.     int left;
  27.     int right;

  28.     cursor = 0;

  29.     while (cursor < len)
  30.     {
  31.         key = list[cursor];
  32.         
  33.         if ( 2 * cursor + 1 < len)
  34.             left = list[2 * cursor + 1];
  35.         else
  36.             left = key + 1;

  37.         if ( 2 * cursor +2 < len)
  38.             right = list[2 * cursor + 2];
  39.         else
  40.             right = key + 2;

  41.         if (key > left && left < right)
  42.         {
  43.             temp = key;
  44.             list[cursor] = left;
  45.             list[cursor * 2 + 1] = temp;
  46.             cursor = cursor * 2 + 1;
  47.         }
  48.         else if (key > right && right < left)
  49.         {
  50.             temp = key;
  51.             list[cursor] = right;
  52.             list[cursor * 2 + 2] = temp;
  53.             cursor = cursor * 2 + 2;
  54.         }
  55.         else
  56.             break;
  57.     }
  58. }

  59. void heapSort(int list[], int len)
  60. {
  61.     int i;
  62.     int temp;

  63.     for (i = 1; i < len; i++)
  64.         minHeapFixup(list, i);

  65.     for (i = len; i > 1; i--)
  66.     {
  67.         temp = list[0];
  68.         list[0] = list[i - 1];
  69.         list[i - 1] = temp;

  70.         minHeapFixdown(list, i - 1);
  71.     }
  72. }
注意这里采用的是最小堆,排序后数组是按递减顺序排列的;如果需要递增顺序,修改为最大堆,或者再进行一次倒置。

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

上一篇:选择排序

下一篇:冒泡排序

给主人留下些什么吧!~~