-
Notifications
You must be signed in to change notification settings - Fork 0
/
heap_k_ary_max.c
105 lines (84 loc) · 1.89 KB
/
heap_k_ary_max.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
98
99
100
101
102
103
104
105
/***********************************************************
Name: Dhruba Saha
Roll No: B.Sc(Sem-IV)-04
Program No: 23A
Program Name: Write a C program to create a k-ary maxheap.
Date: 13/06/2022
***********************************************************/
#include <stdio.h>
#include <stdlib.h>
#define K 3
int parent(int i);
int left(int i);
int right(int i);
void maxheapify(int *a, int i, int n);
void buildmaxheap(int *a, int n);
void inputArr(int *arr, int n);
void printArr(int *arr, int n);
void main() {
int n, *arr;
printf("Enter the number of elements:");
scanf("%d", &n);
arr = (int *)malloc(n * sizeof(int));
inputArr(arr, n);
printf("Before k-ary maxheapify(k=3):\n");
printArr(arr, n);
buildmaxheap(arr, n);
printf("After k-ary maxheapify(k=3):\n");
printArr(arr, n);
}
int parent(int i) { return (i - 1) / K; }
int left(int i) { return (2 * i + 1); }
int right(int i) { return (2 * i + 2); }
void maxheapify(int *a, int i, int n) {
int l = left(i);
int r = right(i);
int largest;
if (l < n && a[l] > a[i])
largest = l;
else
largest = i;
if (r < n && a[r] > a[largest])
largest = r;
if (largest != i) {
int temp = a[i];
a[i] = a[largest];
a[largest] = temp;
maxheapify(a, largest, n);
}
}
void buildmaxheap(int *a, int n) {
for (int i = n / 2 - 1; i >= 0; i--)
maxheapify(a, i, n);
}
void inputArr(int *arr, int n) {
int i;
for (i = 0; i < n; i++) {
printf("Enter the element %d:\n", i + 1);
scanf("%d", &arr[i]);
}
}
void printArr(int *arr, int n) {
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/*
Output:
Enter the number of elements:5
Enter the element 1:
10
Enter the element 2:
4
Enter the element 3:
23
Enter the element 4:
56
Enter the element 5:
31
Before k-ary maxheapify(k=3):
10 4 23 56 31
After k-ary maxheapify(k=3):
56 31 23 4 10
*/