I have tried to implement my Heap in C. The following are the 13 operations defined:
- build_maxheap
- insert
- exctract_max (delete heap max root)
- max_delete (delete an element or key)
- max_heapify
- clear
- heapSort
- get_max
- increase_key (helper function for insert and delete key functions)
- height
- is_empty
- is_maxheap (checks if the array is a heap)
This is the code in C:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
typedef struct MaxHeap {
int size;
int* heap;
} MaxHeap;
const MaxHeap maxheap_init = { .size = 0, .heap = NULL };
int INF = 1000, N_INF = -1000;
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
int parent(int i) {
return (i-1)/2;
}
int left(int i) {
return (2*i + 1);
}
int right(int i) {
return (2*i + 2);
}
int get_max(MaxHeap* max_heap) { //O(1)
return max_heap->heap[0];
}
int is_empty(MaxHeap* max_heap) {
return max_heap->heap[0] == N_INF;
}
int height(MaxHeap* max_heap) {
return floor(log2(max_heap->size));
}
MaxHeap* create_maxheap(int size) {
MaxHeap* heap = calloc(size, sizeof * heap);
if (!heap) return heap;
heap->size = size;
return heap;
}
void max_heapify(int* data, int* key_index, int i, int size) { // O(logn)
int largest = i, leftie = left(i), rightie = right(i);
if (leftie < size && data[leftie] > data[largest])
largest = leftie;
if (rightie < size && data[rightie] > data[largest])
largest = rightie;//transitvity
if (largest != i) {
swap(&data[i], &data[largest]);
//
key_index[data[i]] = i;
key_index[data[largest]] = largest;
//
max_heapify(data, key_index, largest, size);
}
}
void increase_key(MaxHeap* max_heap, int* key_index, int j, int key) {
if (key < max_heap->heap[j])
printf("Error: key must be larger \n");
else {
max_heap->heap[j] = key;
key_index[key] = j;
for (int i = j; i > 0; i = parent(i)) {
if (max_heap->heap[i] > max_heap->heap[parent(i)]) {
swap(&max_heap->heap[i], &max_heap->heap[parent(i)]);
key_index[max_heap->heap[i]] = i;
key_index[max_heap->heap[parent(i)]] = parent(i);
}
else break;
}
}
}
int* build_max_heap(int* data, int* key_index, int size) { //O(n)
for (int i = size / 2 - 1; i >= 0; i--) {
max_heapify(data, key_index, i, size);
}
return data;
}
void insert(MaxHeap* max_heap, int* key_index, int key) { // O(logn)
int* temp = realloc (max_heap->heap, (max_heap->size + 1) * sizeof (*(max_heap->heap)));
if (temp) {
max_heap->heap = temp;
max_heap->heap[max_heap->size] = N_INF;
increase_key(max_heap, key_index, max_heap->size, key);
max_heap->size += 1;
temp = 0;
}
}
void extract_max(MaxHeap* max_heap, int* key_index) { // O(logn)
swap(&max_heap->heap[0], &max_heap->heap[max_heap->size - 1]);
max_heap->size -= 1;
max_heapify(max_heap->heap, key_index, 0, max_heap->size);
}
void delete_key(MaxHeap* max_heap, int* key_index, int key) { //O(logn)
int index = key_index[key];
increase_key(max_heap, key_index, index, INF);
extract_max(max_heap, key_index);
}
void clear(MaxHeap* max_heap) {
for (int i = 0; i < max_heap->size; i++)
max_heap->heap[i] = N_INF; //assuming it is never in the heap
max_heap->size = 0;
}
void print_heap(MaxHeap* max_heap) { // O(n)
int size = max_heap->size;
if (size % 2 != 0)
size = size + 1;
for (int i = 0; i < size/2 - 1; i++) {
printf("Parent: %d -> Left: %d | Right: %d \n", max_heap->heap[i], max_heap->heap[2*i+1], max_heap->heap[2*i+2]);
}
int j = max_heap->size/2 - 1;
if (max_heap->size % 2 == 0)
printf("Parent: %d -> Left: %d \n", max_heap->heap[j], max_heap->heap[2*j+1]);
}
int is_maxheap(MaxHeap* max_heap) { // O(n)
for (int i = max_heap->size-1; i > 0 ; i--) {
if (max_heap->heap[i] > max_heap->heap[parent(i)]) {
return 0;
}
}
return 1;
}
void heap_sort(MaxHeap* max_heap, int* key_index) { // assumes already a max heap as argument
// if the input is not a heap, call build_max_heap()
for (int i = max_heap->size - 1; i >= 0; i--) {
swap(&max_heap->heap[0], &max_heap->heap[i]);
max_heapify(max_heap->heap, key_index, 0, i);
}
}
void print_arr(MaxHeap* max_heap) {
for (int i = 0; i < max_heap->size; i++)
printf("%d ", max_heap->heap[i]);
printf("\n");
}
int main() {
int size = 6, MAX_Key = INF, elements[6] = {10, 20, 15, 12, 40, 25};
int* data = calloc(size, sizeof * data);
if (!data) return 0;
for (int i = 0; i < size; i++)
data[i] = elements[i];
int* key_index = calloc(MAX_Key, sizeof * key_index); // we assume key > 0, if key < 0, then we add an additional array
if (!key_index) return 0;
for (int i = 0; i < size; i++)
key_index[elements[i]] = i;
MaxHeap max_heap = maxheap_init;
max_heap.size = size;
max_heap.heap = build_max_heap(data, key_index, size);
print_heap(&max_heap);
printf("is_max_heap: %d \n", is_maxheap(&max_heap));
extract_max(&max_heap, key_index);
printf("is_max_heap: %d \n", is_maxheap(&max_heap));
print_heap(&max_heap);
insert(&max_heap, key_index, 14);
printf("is_max_heap: %d \n", is_maxheap(&max_heap));
print_heap(&max_heap);
delete_key(&max_heap, key_index, 14);
printf("is_max_heap: %d \n", is_maxheap(&max_heap));
print_heap(&max_heap);
printf("height: %d \n", height(&max_heap));
printf("max: %d \n", get_max(&max_heap));
heap_sort(&max_heap, key_index);
print_arr(&max_heap);
clear(&max_heap);
printf("is empty: %d \n", is_empty(&max_heap));
free(data);
free(key_index);
return 0;
}
If you have any improvement ideas, I would be very grateful to read through them. I should note that this implementation is for learning purposes, not for a client or something. There might be some place when I missed some secondary check for an empty array or something, but I am interested in seeing if the code holds or not. I tested it and it works just fine.
