Cílem úlohy je seznámit se s realizací prioritní fronty haldou a využit princip haldy v implementaci řazení v HeapSortu (řazení haldou). Pro jednoduchost jsou uvažována pouze celá čísla v rozsahu 0 až 4294967294 (UINT_MAX-1, viz limits.h), která zároveň definují priority, nižší číslo má vyšší priority (min-heap). Řešení se skládá z implementace rozhraní pq_heap.h do samostatné dynamické knihovny libpq_heap.so a programu, který načte vstupní čísla ze stdin a zapíše je vzestupně na stdout. Součástí výchozích souboru jsou kromě rozhraní pq_heap.h také binární programy generující vstup, refereční řešení a testovací program dynamicky linkovaný k příslušené variantě¹⁾ knihovny libpq_heap.so.

Datová struktura halda (heap) je plný binární strom reprezentovaný v poli pevné délky splňující vlastnost haldy, viz lec09. Pro tzv. min haldu tedy platí, že libovolný uzel strom má hodnotu nižší než jeho levý nebo pravý následník, pokud existují, a kořen stromu je tedy prvek s nejnižší hodntou.

Implementace řazení haldou je možné realizovat funkcí heapify nad existující haldou, pole valso n prvcích.

Implementace načtení hodnot a jejich vytištění v roustoucím pořadí postačí načtené hodnoty vkládat do priortiní fronty funkcí pq_push() a po načtení je postupně vyjímat funkcí pq_pop() a tisknout na stdout.

Součástí knihovny pq_heap jsou následující funkce pro práci s prioritní frontou.

• Funkce pq_alloc() vytvoření datové struktury prioritní fronty.
• Funkce pq_release() uvolnění alokované paměti struktury prioritní fronty.
• Funkce pq_size() vrací počet prvků v prioritní frontě.
• Funkce pq_is_empty() test, zdali je prioritní fronta prázdná.
• Funkce pq_push() vložení prvku do prioritní fronty.
• Funkce pq_pop() vyjmutí nejprioritnějšího (nejmenšího) prvku z prioritní fronty.
• Funkce pq_peek() vrací hodnotu nejprioritnějšího (nejmenšího) prvku prioritní fronty.
• Funkce pq_seek() vrací hodnotu prvku v poli priortní fronty haldy na předané pozici v poli.
• Funkce pq_heapify() uspořádá akutální pole haldy vzestupně.

#include <inttypes.h>
 
/*
 * Initialize priority queue (pq) structure using heap as full binary tree implemented in array to store up to  the capacity items.
 *
 * return pointer to the dynamically allocated pq structure or NULL on a failure
 */
void *pq_alloc(uint32_t capacity);
 
/*
 * Release all allocated memory of the passed
 * pq structure that is supposed to be allocated by 
 * pq_alloc()
 */
void pq_release(void *pq);
 
/* 
 * Return number of items in the pq
 */
uint32_t pq_size(const void *pq);
 
/*
 * Return true if pq is empty
 */
_Bool pq_is_empty(const void *pq);
 
/* 
 * Insert the passed value v into the priority queue
 * according to its value. 
 *
 * Return true on success; otherwise false, e.g., pq is full).
 */
_Bool pq_push(void *pq, uint32_t v);
 
/* The priority queue (pq) is supposed to be implemented by min-heap, the item with the lowest value (priority) is popped first.
 *
 * Return true on success; otherwise false, e.g., pq is empty).
 */
_Bool pq_pop(void *pq, uint32_t *v);
 
/* 
 * Return the top item from the pq.
 * Function fail if call on empty queue
 */ 
uint32_t pq_peek(void *pq);
 
/* 
 * Return the item value from the seek index of the heap array
 * Function fail if seek is out of range.
 * For seek = 0, it behaves as pq_peek()
 *
 */ 
uint32_t pq_seek(void *pq, uint32_t seek);
 
/* 
 * Sort the internal representation using heap property, such that 
 * the complexity can be bounded by O(n log2 n). 
 * When heapifid, pq_seek for 0..pq_size() returns sorted values 
 */ 
void pq_heapify(void *pq);

Odevzdávejte pouze soubor pq_heap.cs implementací prioritní fronty haldou. Soubory uložte přímo do zip archivu a nevytvářejte žádné složky. Správnost implementace bude ověřena testovacím programem.

Povinné soubory:

• pq_heap.c - implementace rozhraní dle výchozího souboru pq_heap.h.

Pro jednodušší testování jsme připravili testovací prgram bab36prga-hw9-test, který linkuje dynamickou knihovnu libpq_heap.so s implementací prioritní fronty a volá příslušené rozhraní a porovnává hodnoty ve frontě s referenčním řešením. Program zároveň testuje řazení a porovnává rychlost řazení, která je očekávána v rozsahu +/- 10 % času referečního řešení.

Referenční program bab36prga-hw9-genref lze použít pro generování náhodné posloupnosti celých čísel přepínačem -generate a uvedením počtu čísel, např. ./bab36prga-hw9-genref -generate 1000.

ldd ./binaries/bab36prga-hw9-test
	linux-vdso.so.1 (0x00007b10c68ef000)
	libm.so.6 => /lib/x86_64-linux-gnu/libm.so.6 (0x00007b10c67d9000)
	libpq_heap.so => ./libpq_heap.so (0x00007b10c67d4000)
	libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007b10c6400000)
	/lib64/ld-linux-x86-64.so.2 (0x00007b10c68f1000)

./bab36prga-hw9-test
Basic test ........... PASSED
Multiple queues test . PASSED
Sort basic test ...... PASSED
DEBUG: Generate 42949672 random values in 5.8 seconds
DEBUG: Solution sort time  16.9 seconds
DEBUG: Reference sort time 16.6 seconds
DEBUG: Difference is 1.8 %
Sort time test ....... PASSED
All tests passed

clang -pedantic -Wall -O3 -std=gnu11 -g main.c -Wl,-rpath=. libpq_heap-fbsd.so -o main
 
./binaries/bab36prga-hw9-genref -generate 10000000 > /tmp/
 
time ./main </tmp/in >/tmp/out2
./main < /tmp/in > /tmp/out2  3.49s user 0.08s system 99% cpu 3.574 total
 
time sort -n /tmp/in > /tmp/out
sort -n /tmp/in > /tmp/out  20.54s user 0.94s system 99% cpu 21.475 total
 
time gsort -n /tmp/in > /tmp/out
gsort -n /tmp/in > /tmp/out  10.28s user 0.79s system 392% cpu 2.821 total