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  about 8 years ago 
Repo Last Updated  about 2 years ago 
Size  260 KB 
Organization / Author  valyala 
Contributors  1 
Page Updated  20180312 
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 subheap 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/sophisticatedgheap branch, which contains sophisticated gheap implementation with more complex heap layout and lowlevel optimizations.
=============================================================================== The implementation provides the following functions:
Auxiliary functions:
STLlike functions:
Heapbased 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 D4 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);