I have an assignment that asks me to implement a priority queue
with binary heap in c. I have a problem because basically, the
input data that we get looks like this...
This 1st paragraph is already a sign of problems. There is no relation between the 2 sentences: priority queue implemented via binary heap is one thing.
The particular form of input data has nothing to do with the task and is other thing.
You should not mix them. Do it only leads to problems.
TL;DR;: I will write below a possible implementation for this. Since I will be coding along this can be a log post. Yes, full code is at the end.
*
the input for the problem
7 - number of occurences
3 4 0 5 8 0 0 - occurences, if the number is 0 that means the number
with highest priority is removed (or if priorities are the same, the
one thats been there the longest - i guess just basic priority queue)
Ian Abbott, kindly left an interpretation of this and this post is based on that.
So the input seems to be a file of nunmbers, where the first value is the number of inputs, followed by them. It is a simple queue and a 0 means to extract the first client in queue. Any non-zero number means to add a new element with that priority to the queue.
The order of arrival is used as an id of the element.
3 4 0 5 8 0 0 interpreted
So the 7 commands goes as
- client
1 enters the queue with priority 3: (1,3)
- client
2 enters the queue with priority 4 and gets the first place (2,4) (1,3)
0: client 2 is extracted- client
3 enter the queue with priority 5 so queue has (3,5) (1,3)
- client
4 enters the queue with priority 8 so queue is (4,8) (3,5) (1,3)
0: client 4 is extracted0: client 3 is extracted- service ends with client
1 left in queue
A priority queue
Let us use some definition:
A priority queue is a data structure for maintaining a set S of x elements, each
with an associated value called a key k. A max-priority queue supports the following
operations:
INSERT( S, x )
MAXIMUM( S )
EXTRACT-MAX( S )
INCREASE-KEY( S, x, k )
From Cormen et al - Introduction to Algorithms, 3rd edition ISBN 978 0 262 03384 8 , page 162
A priority queue as a heap
Let us consider a heap as an array of pointers, so we can use a heap of anything: ints, structs et. al. And consider these functions, with the obvious meanings:
typedef int(F_compare)(const void*, const void*);
typedef struct
{ // heap: as a vector of pointers
void** H; // the heap itself
unsigned size; // current size
unsigned capacity;
unsigned increment;
unsigned limit;
F_compare* f_cmp; // Max_Heap? Min_Heap?
} Heap;
Heap* hp_destroy(Heap*);
int hp_build_max_heap(Heap*);
Heap* hp_create(
unsigned initial, unsigned increment, unsigned limit,
F_compare* f);
void* hp_extract_max(Heap* heap);
int hp_insert(void* elem, Heap* heap);
int hp_is_max_heap(Heap* heap, unsigned root);
int hp_max_heapify(Heap* heap, unsigned index);
int hp_heapSort(Heap* heap);
So our heap is extensible, from an initial size up to a limit in steps of increment.
For computing order we use a compare function, like qsort does. The usual way.
our heap element is a simple struct
typedef struct
{
unsigned id;
unsigned priority;
} Element;
int f_cmp_el(const void* a, const void* b);
The compare function is trivial:
int f_cmp_el(const void* a, const void* b)
{
const Element* one = a;
const Element* other = b;`
if (one->priority > other->priority) return -1;
if (one->priority == other->priority) return 0;
return 1;
}
since we just need to compare the priorities.
building the example program
If we have this heap implemented, then the program is just a matter of building a heap with the values, and extracting the first in queue at each 0.
consuming the numbers
#include <stdio.h>
int process(const char* input);
int main(void)
{
const char in_file[] = "in.txt";
int res = process(in_file);
printf("main(): %d commands processed from \"%s\"\n", res,in_file);
return 0;
}
int process(const char* input)
{
static int size = 0;
FILE* in = fopen(input, "r");
if (in == NULL) return -1;
int res = 0;
int value = 0;
res = fscanf(in, "%d", &value);
if (res != 1)
{
fclose(in);
return -2;
}
printf("%d commands in \"%s\"\n", value,input);
int ok = 0;
while (value > ok)
{
int cmd = 0;
res = fscanf(in, "%d", &cmd);
if (res < 0) break;
if (res != 1) continue;
printf(" command: %d\n", cmd);
++ok;
}
return ok;
fclose(in);
return 0;
}
For in.txt as the input in the original post
7
3 4 0 5 8 0 0
this code shows
7 commands in "in.txt"
command: 3
command: 4
command: 0
command: 5
command: 8
command: 0
command: 0
main(): 7 commands processed from "in.txt"
using the numbers as commands
A change in process can check for the command and call the heap functions as needed.
This program does that:
#include <stdio.h>
#include "aheap.h"
typedef struct
{
unsigned id;
unsigned priority;
} Element;
int f_cmp_el(const void* a, const void* b);
int process(const char* input);
int main(void)
{
const char in_file[] = "in.txt";
int res = process(in_file);
printf(
"main(): %d commands processed from \"%s\"\n", res,
in_file);
return 0;
}
int process(const char* input)
{
FILE* in = fopen(input, "r");
if (in == NULL) return -1;
int res = 0;
int value = 0;
res = fscanf(in, "%d", &value);
if (res != 1)
{
fclose(in);
return -2;
}
printf("%d commands in \"%s\"\n", value, input);
Heap* my_heap = hp_create(100, 100,
1000, f_cmp_el);
if (my_heap == NULL)
{
fprintf(stderr, "Error creating queue! Aborting\n");
fclose(in);
return -3;
}
int ok = 0;
Element* next = NULL;
int nsu = 0;
while (value > ok)
{
int cmd = 0;
res = fscanf(in, "%d", &cmd);
if (res < 0) break;
if (res != 1) continue;
switch (cmd)
{
case 0: // serve one client
next = (Element*) hp_extract_max(my_heap);
if (next == NULL)
{
printf(
" No element in queue\n");
break;
}
printf(
" %d removed from the queue. Priority is %d\n",
next->id, next->priority);
break;
default:
next = malloc(sizeof(Element));
if (next == NULL) { break; }
next->id = ++nsu;
next->priority = cmd;
res = hp_insert(next, my_heap);
printf(" %d entered the queue. Priority %d\n", next->id, next->priority);
break;
}; // case
++ok;
}
hp_destroy(my_heap);
return ok;
fclose(in);
return 0;
}
int f_cmp_el(const void* a, const void* b)
{
const Element* one = a;
const Element* other = b;
if (one->priority > other->priority) return -1;
if (one->priority == other->priority) return 0;
return 1;
}
There is not much logic in it:
- if the command is
0 then calls hp_extract_max(). It is a priority queue so that is all we need.
- if the command is a number then it is a new client with such priority so an
Element is build and passed to hp_insert().
output
7 commands in "in.txt"
1 entered the queue. Priority 3
2 entered the queue. Priority 4
2 removed from the queue. Priority is 4
3 entered the queue. Priority 5
4 entered the queue. Priority 8
4 removed from the queue. Priority is 8
3 removed from the queue. Priority is 5
main(): 7 commands processed from "in.txt"
an implementation for the heap
the header aheap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "memory.h"
typedef int(F_compare)(const void*, const void*);
typedef struct
{ // heap: as a vector of pointers
void** H; // the heap itself
unsigned size; // current size
unsigned capacity;
unsigned increment;
unsigned limit;
F_compare* f_cmp; // Max_Heap? Min_Heap?
} Heap;
Heap* hp_create(
unsigned initial, unsigned increment, unsigned limit,
F_compare* f);
Heap* hp_destroy(Heap*);
int hp_build_max_heap(Heap*);
int hp_empty(Heap*);
void* hp_extract_max(Heap* heap);
int hp_insert(void* elem, Heap* heap);
int hp_is_max_heap(Heap* heap, unsigned root);
int hp_max_heapify(Heap* heap, unsigned index);
int hp_heap_sort(Heap* heap);
a possible implementation in aheap.c
#include <stdio.h>
#include "aheap.h"
Heap* hp_destroy(Heap* heap)
{
free(heap->H);
free(heap);
return NULL;
};
int hp_build_max_heap(Heap* heap)
{
for (unsigned i = heap->size / 2; i > 0; i -= 1)
hp_max_heapify(heap, i);
return 0;
};
Heap* hp_create(
unsigned init, unsigned inc, unsigned lim, F_compare* f)
{
if (init == 0) return NULL; // for sanity
if (lim == 0) return NULL;
if (lim < init) lim = init;
Heap* novo = (Heap*)malloc(sizeof(Heap));
if (novo == NULL) return NULL;
novo->f_cmp = f;
novo->capacity = init; // sure
novo->limit = lim;
novo->increment = inc;
novo->size = 0;
novo->H = (void*)malloc((1 + init) * sizeof(void*));
for (unsigned i = 0; i <= init; i += 1)
novo->H[i] = NULL;
return novo;
}
int hp_empty(Heap* heap)
{
if (heap == NULL) return 0;
return heap->size == 0;
}
void* hp_extract_max(Heap* heap)
{
if (heap->size <= 0) return NULL;
// index 0 is not used
heap->H[0] = heap->H[1];
heap->H[1] = heap->H[heap->size];
heap->size -= 1;
hp_build_max_heap(heap);
return heap->H[0];
};
int hp_insert(void* element, Heap* heap)
{
// full?
if (heap->size >= heap->limit) return -1;
// can it grow?
if (heap->size >= heap->capacity)
{
if (heap->increment == 0) return -1;
if ((heap->increment + heap->capacity) >
heap->limit)
return -1;
// ok:
unsigned n_atual = heap->capacity;
unsigned n_novo = n_atual + heap->increment;
// alloc new block
void* novo =
realloc(heap->H, (1 + n_novo) * sizeof(void*));
if (novo == NULL) return -2;
heap->H = (void**)novo;
heap->capacity = n_novo;
}
heap->size += 1;
heap->H[heap->size] = element;
return hp_build_max_heap(heap);
};
int hp_is_max_heap(Heap* heap, unsigned root)
{
unsigned esq = root + root; // 2n
unsigned dir = 1 + esq; // 2n + 1
if (esq > heap->size) return 1;
if (dir > heap->size) return 1;
// violation
if (heap->f_cmp(heap->H[esq], heap->H[root]) == -1)
return 0;
// violation
if (heap->f_cmp(heap->H[dir], heap->H[root]) == -1)
return 0;
return (hp_is_max_heap(heap, esq) +
hp_is_max_heap(heap, dir)) == 2;
};
int hp_max_heapify(Heap* heap, unsigned root)
{
unsigned maior = root;
void* temp;
unsigned esq = root + root; // 2n
unsigned dir = 1 + esq; // 2n + 1
if (esq > heap->size) return 0;
maior = (heap->f_cmp(heap->H[esq], heap->H[root]) == -1)
? esq
: root;
if (esq != (heap->size))
{
if (heap->f_cmp(heap->H[dir], heap->H[maior]) == -1)
maior = dir;
}
if (maior != root)
{
temp = heap->H[root];
heap->H[root] = heap->H[maior];
heap->H[maior] = temp;
hp_max_heapify(heap, maior);
} // end if
return 0;
};
int hp_heap_sort(Heap* heap)
{
while (heap->size > 1)
{
void* greatest = hp_extract_max(heap);
// poe de volta no final
heap->H[1 + heap->size] = greatest;
}
return 0;
}
