Number of watchers on Github | 59 |
Number of open issues | 3 |
Main language | C++ |
Open pull requests | 1+ |
Closed pull requests | 0+ |
Last commit | over 7 years ago |
Repo Created | almost 8 years ago |
Repo Last Updated | almost 2 years ago |
Size | 260 KB |
Organization / Author | valyala |
Contributors | 1 |
Page Updated | 2018-03-12 |
Do you use gheap? Leave a review! | |
View open issues (3) | |
View gheap activity | |
View on github | |
Fresh, new opensource launches 🚀🚀🚀 | |
Trendy new open source projects in your inbox!
View examples
|
Generalized heap implementation
Generalized heap is based on usual heap data structure - http://en.wikipedia.org/wiki/Heap_%28data_structure%29 .
It provides two additional paremeters, which allow optimizing heap for particular cases:
Fanout. The number of children per each heap node.
PageChunks. The number of chunks per each heap page. Each chunk contains Fanout items, so each heap page contains (PageChunks * Fanout) items. Items inside heap page are organized into a sub-heap with a root item outside the page. Leaf items in the page can be roots pointing to another pages.
See also https://github.com/valyala/gheap/tree/sophisticated-gheap branch, which contains sophisticated gheap implementation with more complex heap layout and low-level optimizations.
=============================================================================== The implementation provides the following functions:
Auxiliary functions:
STL-like functions:
Heap-based algorithms:
The implementation is inspired by http://queue.acm.org/detail.cfm?id=1814327 , but it is more generalized. The implementation is optimized for speed. There are the following files:
Don't forget passing -DNDEBUG option to the compiler when creating optimized builds. This significantly speeds up gheap code by removing debug assertions.
There are the following tests:
=============================================================================== gheap for C++ usage
gheap.hpp
...
template
typedef gheap<2, 1> binary_heap;
heapsort
typedef gheap<4, 1> d4_heap;
heapsort
typedef gheap<2, 512> paged_binary_heap;
heapsort
=============================================================================== gheap for C usage
gheap.h
static void less(const void *const ctx, const void *const a, const void *const b) { (void)ctx; return *(int *)a < *(int *)b; }
static void move(void *const dst, const void *const src) { *(int *)dst = *(int *)src; }
static void heapsort(const struct gheap_ctx *const ctx, int *const a, const size_t n) { gheap_make_heap(ctx, a, n); gheap_sort_heap(ctx, a, n); }
/* heapsort using binary heap */ static const struct gheap_ctx binary_heap_ctx = { .fanout = 2, .page_chunks = 1, .item_size = sizeof(int), .less_comparer = &less, .less_comparer_ctx = NULL, .item_mover = &move, }; heapsort(&binary_heap_ctx, a, n);
/* heapsort using D-4 heap */ static const struct gheap_ctx d4_heap_ctx = { .fanout = 4, .page_chunks = 1, .item_size = sizeof(int), .less_comparer = &less, .less_comparer_ctx = NULL, .item_mover = &move, }; heapsort(&d4_heap_ctx, a, n);
/* heapsort using paged binary heap */ static const struct gheap_ctx paged_binary_heap_ctx = { .fanout = 2, .page_chunks = 512, .item_size = sizeof(int), .less_comparer = &less, .less_comparer_ctx = NULL, .item_mover = &move, }; heapsort(&paged_binary_heap_ctx, a, n);