-
Notifications
You must be signed in to change notification settings - Fork 4
/
max-heap.c
97 lines (78 loc) 路 1.73 KB
/
max-heap.c
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
#include "max-heap.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int Parent(int i) { return i >> 1; }
int Left(int i) { return (i << 1) + 1; }
int Right(int i) { return (i << 1) + 2; }
void Swap(int *A, int i, int j) {
int temp;
temp = A[i];
A[i] = A[j];
A[j] = temp;
}
int Max(heap *heap) { return heap->a[0]; }
int ExtractMax(heap *heap) {
int max = Max(heap);
Swap(heap->a, 0, heap->heap_size - 1);
heap->heap_size--;
MaxHeapify(heap, 0);
return max;
}
heap *AllocateMaxHeap(int size) {
heap *heap = malloc(sizeof heap);
heap->a = malloc(size * sizeof(int));
heap->heap_size = 0;
heap->size = size;
return heap;
}
void DestroyMaxHeap(heap *heap) {
free(heap->a);
free(heap);
}
void MaxHeapify(heap *heap, int i) {
int l, r, largest;
int *a = heap->a;
l = Left(i);
r = Right(i);
largest = i;
if (l >= heap->heap_size)
return;
if (l < heap->heap_size && a[i] < a[l])
largest = l;
if (r < heap->heap_size && a[largest] < a[r])
largest = r;
if (largest == i)
return;
Swap(a, i, largest);
MaxHeapify(heap, largest);
}
void BuildMaxHeap(heap *heap) {
int i;
i = heap->heap_size / 2;
while (i >= 0)
MaxHeapify(heap, i), i--;
}
void IncreaseKey(heap *heap, int i) {
int *a = heap->a;
while (a[Parent(i)] < a[i]) {
Swap(a, i, Parent(i));
i = Parent(i);
}
}
void MaxHeapInsert(heap *heap, int key) {
heap->a[heap->heap_size] = key;
IncreaseKey(heap, heap->heap_size);
heap->heap_size++;
}
void HeapSort(int *A, int size) {
heap *heap = malloc(sizeof heap);
heap->a = A;
heap->heap_size = size;
heap->size = size;
int i;
BuildMaxHeap(heap);
for (i = heap->heap_size - 1; i >= 0; i--)
A[i] = ExtractMax(heap);
free(heap);
}