A C project implementing core data structures and graph algorithms, including an experimental comparison of two priority-queue representations inside Dijkstra's shortest-path algorithm.
Context: Algorithms and Data Structures coursework, University of São Paulo (USP), 2025
Language: C
- singly linked list;
- binary min/max heap with dynamic growth;
- priority queue with heap-backed and linked-list-backed representations;
- weighted undirected graph using adjacency lists;
- lazy Dijkstra shortest paths;
- in-place heapsort.
The same Dijkstra implementation is evaluated with two priority-queue backends: a binary heap and a linked list.
With the heap-backed queue, the minimum-priority element is available at the root. With the list-backed queue, finding the minimum requires scanning the list. Dijkstra is implemented lazily: improved distances are inserted as new queue entries and stale entries are discarded after removal.
The original report compares the two priority-queue backends on randomly weighted undirected graphs with 100 vertices. A larger run of 10,000 executions reported:
| Metric | Heap-backed PQ | Linked-list PQ |
|---|---|---|
| Mean | 130.320 µs | 675.975 µs |
| Median | 127.219 µs | 665.626 µs |
| Standard deviation | 16.300 µs | 61.935 µs |
| 95% CI - lower | 130.001 µs | 674.761 µs |
| 95% CI - upper | 130.639 µs | 677.189 µs |
The mean runtime ratio was approximately 5.19x (list / heap) for that experiment.
The plots and aggregate values come from the original 2025 report. The raw 10,000 timing samples and the plotting script are no longer available. The full report is available in docs/original-report-pt.pdf.
makeThe Makefile compiles the modules with:
-std=c11 -Wall -Wextra -Wpedantic
and produces build/libalgorithms.a.
make cleanremoves generated objects and the library.
algorithms-performance-analysis/
├── README.md
├── Makefile
├── include/
├── src/
├── results/
│ ├── heap-runtime-distribution.png
│ └── list-runtime-distribution.png
└── docs/
└── original-report-pt.pdf