{{indexmenu_n>9}}
======== HW 9 - Řazení haldou (Heap Sort) ========


^ Termín odevzdání | <wrap important>17.05.2025@23:59 PDT</wrap>|
^ Povinné zadání |  3b |
^ Volitelné zadání | Není |
^ Bonusové zadání |   Není |
^ Počet uploadů |  20 | 
^ Výchozí soubory |  {{ :courses:bab36prga:hw:bab36prga-hw9.zip |}} |

<note tip>Podklady pro prioritní frontu jsou v přednášce věnované prioritní frontě. [[https://cw.fel.cvut.cz/wiki/courses/bab36prga/lectures/start#|]].</note>
=====  Povinné zadaní ===== 

Cílem úlohy je seznámit se s realizací prioritní fronty haldou a využit princip haldy v implementaci řazení v HeapSortu ([[https://cs.wikipedia.org/wiki/%C5%98azen%C3%AD_haldou|ř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ě((Dle podporovaného OS.)) knihovny ''libpq_heap.so''.

<note tip>Jako refereční řešení lze použít také dostupný nástroj ''sort'' s přepínačem numerického řazení ''-n'', viz [[https://www.man7.org/linux/man-pages/man1/sort.1.html|man sort]].</note>

Datová struktura halda (//heap//) je plný binární strom reprezentovaný v poli pevné délky splňující **<fc #ff0000>vlastnost haldy</fc>**, viz [[https://cw.fel.cvut.cz/wiki/courses/bab36prga/lectures/start#abstraktni_datovy_typ_adt_-_zasobnik_fronta_prioritni_fronta|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 [[https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation|řazení haldou]] je možné realizovat funkcí ''heapify'' nad existující haldou, pole ''vals''o //n// prvcích.

<note tip>Z pohledu implementace prioritní fronty haldou v poli ''vals'' o //n// prvcích, můžeme implementovat i tak, že postupně zaměňuje hodnotu kořene, ''vals[0]'' s prvkem na konci pole ''vals[n-1]'' a nový kořen zaměňuje v poli o uvažované velikosti ''n-1'' podobně jako při operaci ''pq_pop()'' tak, aby platila vlastnost haldy. Postupně tak zkracujeme uvažovanou délku pole haldy a postupnou záměnou všech //n// prvků jsou hodnoty v poli uspořádány **sestupně**. Proto následně pro zachování vlastnosti haldy na původním polem o velikosti //n// obrátíme pořadí prvků.
</note>

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ě.

<note important>Volání ''pq_peek()'' a ''pq_seek()'' vyžaduje alespoň jeden prvek ve frontě. Rozhraní neumožňuje indikovat nevhodné volání návratovou hodnoutou. Proto v případě volání na prázdnou frontou je možné program předčasně ukončit voláním ''exit()'', např. s hodnotou ''EAGAIN'' tak, jako v referenčním řešení.</note>
==== Rozhraní definované v souboru ''pq_heap.h'' ====

<code c>
#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);
</code>


===== Odevzdávané soubory =====

Odevzdávejte pouze soubor ''pq_heap.c''s 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.

**<fc #ff0000>Povinné soubory</fc>**:

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

===== Způsob testování =====

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''.

<note tip>
Příklad prostředí s knihovnou ''libpq_heap.so'' a testovacím programem ''binaries/bab36prga-hw9-test'' 
<code shell>
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)
</code>
Spuštění testu vůči knihovně ''libpq_heap.so'' v aktuálním pracovním adresáři může vypadat například následovně.
<code shell>
./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
</code>
</note>


<note>
Programem ''bab36prga-hw9-genref'' můžeme vygenerovat větší testovací soubor, který uložíme do [[https://cs.wikipedia.org/wiki/RAMDisk|ramdisku]] v adresáři ''/tmp''. Nástrojem ''time'' můžeme změřit výkon řazení s využitím vlastní nebo výchozí prioritní fronty, například následovně.
<code shell>
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
</code>
Kde si můžeme všimnout, že nástroj ''gsort'' je na daném stroji výrazně rychlejší, neboť využívá téměř 4 jádra procesoru. Naopak standardní  ''sort'' je mnohem pomalejší než naše implementace.
</note>
====== Odevzdání a hodnocení ======

/* Veřejné příklady + Makefile: {{ :courses:bab36prga:hw:b3b36prg-hw08.zip |}} */

^  ^  Povinné zadání  ^
^ Název v BRUTE |   HW9  |
^ Odevzdávané soubory |  pq_heap.c  |
^ Argumenty při spuštění |  žádné  	  |
^ Kompilace  |  clang -pedantic -Wall -Werror -std=<fc #ff0000>gnu99</fc> -O2 -g |
^ Procvičované oblasti |  datové struktury \\ práce s polem  |