-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathheap.c
More file actions
98 lines (85 loc) · 2.22 KB
/
heap.c
File metadata and controls
98 lines (85 loc) · 2.22 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
* =========================================================
* Filename: heap.c
* Description: 堆排序
*
* =========================================================
*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#define SIZE 100 /* heap size */
#define LEFT(i) (2*i + 1)
#define RIGHT(i) (2*i + 2)
typedef struct heapq{ /* step 1.优先队列结构体声明 */
// int arr[SIZE];
int *arr;
int len;
}HeapQ;
/*---------------------------------------------------
* step 2. HeapQ 方法的声明
*---------------------------------------------------*/
HeapQ* heapify(int arr[] , int n);
void adjust(HeapQ* h , int p);
void swap(int *a,int *b);
void heapSort(int arr[], int n);//step 3.堆排序
void printArray(int arr[], int n);
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int size = sizeof(arr)/sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, size);
heapSort(arr, size);
printf("\nSorted array is \n");
printArray(arr, size);
return 0;
}
HeapQ* heapify(int arr[] , int n){
HeapQ* h;
h = malloc(sizeof(HeapQ));
h->len = n;
h->arr = arr;
int i;
// for(i = 0;i < n;i++)// 初始化
// h->arr = arr[i];
for(i = (h->len)/2 - 1;i >= 0;i--)
adjust(h , i);// LEFT(i) RIGHT(i) 已经是堆
return h;
}
void adjust(HeapQ* h , int p){
int min;//小根堆调整策略,较小的上调
while(p <= (h->len)/2 - 1){
min = p;
if(LEFT(p) < h->len && h->arr[LEFT(p)] < h->arr[min])
min = LEFT(p);
if(RIGHT(p) < h->len && h->arr[RIGHT(p)] < h->arr[min])
min = RIGHT(p);
if(min == p)
break;
else{
swap(h->arr + p,h->arr + min);
p = min;
}
}
}
void heapSort(int arr[], int n){//step 3.堆排 小根堆做降序,大根堆做升序.这点我没想到
HeapQ* h = heapify(arr,n);
while(h->len > 1){
swap(h->arr , h->arr + (h->len - 1));
--(h->len);
adjust(h , 0);
}
}
inline void swap(int *a,int *b){
int t = *a;
*a = *b;
*b = t;
}
void printArray(int arr[], int n){
int i = 0;
while(i < n){
printf("%d%s",arr[i],(i == n-1)?"\n":" ");
i++;
}
}