• 博客访问： 664373
• 博文数量： 141
• 博客积分： 0
• 博客等级： 民兵
• 技术积分： 1114
• 用 户 组： 普通用户
• 注册时间： 2014-03-17 14:32

2016-02-16 22:15:00

## 二叉堆的定义

1．父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。

2．每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

1. typedef struct struct_heap {

2.     int size;
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];

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. }

0